1

i am writing the function to check if the given value is included in the matrix in . This matrix has the following properties: •Integers in each row are sorted in ascending from left to right. •Integers in each column are sorted in ascending from top to bottom

public static boolean searchMatrix(int target, int[][] matrix)
{
    for(int i = 0;i <= matrix[0].length;i++)
    {
        for (int j=i; j<matrix.length;j++)
        {
        if(target == matrix[i][j])
        return true;
        }
    }
    return false;
}

i want to know weather this program has time complexity of O(N). if not what changes should i make to get into O(N).

Improve this question
5
  • In general if the statements inside the loop are O(1), one loop is O(n) and 2 loops with one nested is O(n^2) or O(n*m). Commented Apr 21, 2017 at 1:18
  • suppose this post will help you to understand the time complexity concept more clearly. Commented Apr 21, 2017 at 1:19
  • @SpencerWieczorek Just curiously asking.. the given matrix is already 2d array which means n is the size of the double array row*column so even though with nested loop wouldnt it beO(n) because the loop will loop n time? Commented Apr 21, 2017 at 1:22
  • In the worst case the nested loop will be run in its entirety once per element in matrix[i] so it is O(N^2) assuming square matrix. Commented Apr 21, 2017 at 1:30
  • @Luminous_Dev It all depends on how you define what N is, but generally you want it something that scales lineally. Stating that N=row*col means that while you could state it's O(N), it's not liner to the size of the matrices row and columns. Commented Apr 21, 2017 at 1:36

5 Answers 5

Reset to default
1

I think the search can be done in linear time. Consider the following 4×4 matrix as a visual:

1 2 4 6
2 3 5 7      ascending from left to right
3 4 6 8      and from top to bottom
4 5 6 9

If we were searching for the value 5 we could begin in the upper left, and then walk to the right until we have either found the value, or encountered a number which is greater than the target of 5. In this case, we hit 6. Then, we can rollback to 4, and advance down to a higher row. It is guaranteed that every previous value in the first row is less than the target and that every value in the next row from that column onwards is greater than the value on the first row.

This is a roughly linear approach. A good analogy would be walking around the perimeter of a mountain, looking for a certain elevation. If at each spot we either don't find the height we want, or find only points too high, we keep walking.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

The way you have it written (brute force computation) has a worst case time complexity of O(N^2). Since you say that the arrays are sorted, you can instead implement binary search which will have a worst case time complexity of N(2*log(N)).

Improve this answer

Comments

0

Assuming a n x m matrix, your algorithm is O(n * m), because it (potentially) iterates all rows and columns (ie all elements).

However, there exists an algorithm that is O(log(m + n)).

Because this is for an on-line coding interview (I am psychic), I will give you hints only:

  • Given elements at coordinate (x, y), what can know about where the target might be?
  • What could you do if you treated x and y separately?
Improve this answer

5 Comments

Hi Glen, please let me know what is wrong with my answer. I think I'm on the right track, but I am on a cell phone right now.
@tim your algorithm is O(n), but you can do it in O(log n). What would happen if instead of starting top left, you started in the middle?
@Bohemian I don't know how you cover all of the possibilities since the rows can have values out of order with the columns. I thought of splitting the matrix into 4 submatrices around the current middle but at each step you only get to eliminate 1 of the 4 matrices and have to search the other 3.
Right, we could use a divide-and-conquer approach, having a bit of a merge sort flavor. In this case, we would start in the middle, and then decide whether we need to go higher or lower. Again, we would land in the middle of that subsection, and repeat. This is O(N lgN)
@tim yes. Work out which quadrant the target is in, then call recursively is the simplest approach.
0

you say the matrix is sorted ,may you can use binary search to find the target . and use two individual one layer loop , firstly search row ,then column.it's o(N/2).

Improve this answer

2 Comments

Note: O(N/2) is the same as O(N).
yes,you are right.but I think it's not a bad implement for the requirement
0

As stated your algorithm is O(N*M) or O(N^2) for a square matrix.

You can do it with a single loop:

Basically starting from the top right you check the cell if the number is too big move left if the number is too small move down. If you fall off the edge on either side the number's not there.

boolean searchMatrix(int target, int[][] mat)
{
   int i = 0, j = mat[0].length;
   while (i < mat.length && j >= 0)
   {
      if (mat[i][j] == target)
      {
         return true;
      }
      else if (mat[i][j] < target)
      {
         i++;
      }
      else
      {
         j--;
      }
   }
   return false;
}
Improve this answer

2 Comments

does this program have jave complexity of O(n)@twain249
The worst case scenario is that you you have to walk N-1 to the left and M-1 down so it's O(M+N-2) or for NxN O(2N-2) which is O(N).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.