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).

user7799918
  • 55
  • 1
  • 1
  • 6
  • 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)`. – Spencer Wieczorek Apr 21 '17 at 01:18
  • suppose this [pos](http://stackoverflow.com/questions/18486543/what-is-the-complexity-of-this-nested-triple-for-loop)t will help you to understand the time complexity concept more clearly. – Rajith Pemabandu Apr 21 '17 at 01: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 be`O(n)` because the loop will loop `n` time? – Luminous_Dev Apr 21 '17 at 01: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. – Paul Back Apr 21 '17 at 01: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. – Spencer Wieczorek Apr 21 '17 at 01:36

5 Answers5

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.

Tim Biegeleisen
  • 502,043
  • 27
  • 286
  • 360
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)).

Community
  • 1
  • 1
Paul Back
  • 1,269
  • 16
  • 23
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?
Bohemian
  • 412,405
  • 93
  • 575
  • 722
  • 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 Biegeleisen Apr 21 '17 at 01:34
  • @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 Apr 21 '17 at 01:38
  • @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. – twain249 Apr 21 '17 at 01:40
  • 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 Biegeleisen Apr 21 '17 at 01:41
  • @tim yes. Work out which quadrant the target is in, then call recursively is the simplest approach. – Bohemian Apr 21 '17 at 02:59
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;
}
twain249
  • 5,666
  • 1
  • 21
  • 26
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).

wylasr
  • 117
  • 9