Searching in a sorted 2D matrix

Question

If I was at an interview, and wrote this code, what would you think? Please be brutal.

Time it took to wrote it: 13 minutes

Problem:

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right. The first integer of each row is greater than the last integer of the previous row. For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

---

 public boolean searchMatrix(int[][] matrix, int target) {
    int lastCol = matrix[0].length-1;
    int row=0;
    while(row!=matrix.length && lastCol>=0){
        if(matrix[row][lastCol]==target){
            return true;
        }
        if(matrix[row][lastCol]>target){
            lastCol--;
            if(binarySearch(matrix[row], 0, lastCol, target)!=-1){
                return true;
            }
        }
        row++;
    }
    return false;
}
public int binarySearch(int[] arr, int low, int high, int target){
    while(low<=high){
        int mid = (low + high)/2;
        if(arr[mid]==target){
            return mid;
        }
        else if(arr[mid]<target){
            low = mid+1;
        }
        else if(arr[mid]>target){
            high = mid-1;
        }
    }
    return -1;
}

Space complexity = \$\mathcal{O}(1)\$
Time Complexity = \$\mathcal{O}(\log(n!))\$

Answer 1

Your algorithm is not efficient (that's the brutal part of the answer).

Searching in a list of t values is a task that can be accomplished using \$\mathcal{O}(\log(t))\$ comparisons. Here we have \$t=m*n\$ values so it should be accomplished using \$\mathcal{O}(\log(m*n)) = \mathcal{O}(\log(m))+\mathcal{O}(\log(n))\$ comparisons. I suspect your algorithm may execute the while loop about matrix.length times so it is not \$\mathcal{O}(\log(m))\$ (where m is the number of rows).

The algorithm could work in the following way:

• If the searched value is smaller then the first column in the first row, then the searched value is not contained in the matrix.
• Then do a binary search on the first column of the matrix to find the largest entry smaller or equal to the searched value.
• If the value found matches, you are done.
• Otherwise, do a binary search on the row found.
• If the value found matches the searched value, you are done;
• otherwise, the searched value is not in the matrix.

Another way is to treat the problem like a single dimension sorted array as it is proposed in the comment of @Azar.

Even a small piece of code can have a lot of errors so it does make sense to try to use library methods to accomplish this task and not implement the binary search by yourself (but I don't know if this is the intention of the poser of the problem).

This blog entry discusses an example of a buggy implementation in Java. It references the following SUN bug report because there was an erroneous implementation of the binary search even in the JDK.

Answer 2

I think it is very well done, especially for 12 minutes.

---

Similar solutions

That solution is very similar to GeekforGeek solution.

https://www.geeksforgeeks.org/search-in-row-wise-and-column-wise-sorted-matrix/

The problem is slightly different (more generic).

Compare

class GFG {

/* Searches the element x in mat[][]. If the
element is found, then prints its position
and returns true, otherwise prints "not found"
and returns false */
private static void search(int[][] mat, int n, int x) {

    int i = 0, j = n - 1; // set indexes for top right
    // element

    while (i < n && j >= 0) {
        if (mat[i][j] == x) {
            System.out.print("n Found at " + i + " " + j);
            return;
        }
        if (mat[i][j] > x) {
            j--;
        } else // if mat[i][j] < x
        {
            i++;
        }
    }

    System.out.print("n Element not found");
    return; // if ( i==n || j== -1 )
}
}
// This code is contributed by Arnav Kr. Mandal.

---

Complexity analysis.

Your complexity analysis was wrong. Let A matrix n x m. The complexity is O(m log(n)).

Proof: For every movement in the vertical direction, the algorithm performs a new binary search in the horizontal direction.

If the matrix is a columnar matrix... the complexity will be O(m), for example.

---

Room for improvement

A better solution would be using the binary search in both directions (what keep working for more generic problems). Complexity is O(log(n) * log(m))

Or take usage of total ordering. More efficient but less generic. Complexity is O(log (n) + log(m))

See: https://www.geeksforgeeks.org/search-element-sorted-matrix/

Answer 3

This is old, but I just happened to see it today.

This answer says that your complexity analysis is wrong. That's not quite true.

Your \$\mathcal{O}(\log(n!))\$ is correct if we assume that \$n\$ is the total amount of data and that \$\mathcal{O}(\log{n^n})\$ is \$\mathcal{O}(\log(n!))\$. That's generally considered to be true because \$n^n\$ is the product of \$n\$ things of magnitude \$n\$ and \$n!\$ is the product of \$n\$ things of average magnitude \$\frac{n}{2}\$. Also \$\mathcal{O}(\log{n^n})\$ is \$\mathcal{O}(n\log{n})\$. We're also assuming that the row and column length can be described as \$\mathcal{O}(n)\$ which is trivially true if their product is \$n\$. But this is a rather loose complexity bound. If the matrix is square, \$\mathcal{O}(\sqrt{n}\log{n})\$ would be tighter.

It is probably simpler and tighter though to describe your algorithm as being \$\mathcal{O}(m\log{n})\$ (or \$\mathcal{O}(\log{n^m})\$) where \$m\$ is the number of rows and \$n\$ is the number of columns (so not the same value as the last paragraph). This entirely gets around any guessing about the shape of the matrix. So \$mn\$ is the number of data elements. And as previously noted, \$\mathcal{O}(\log{mn})\$ is possible (may also be written \$\mathcal{O}(\log{m} + \log{n})\$).

The \$\mathcal{O}(m\log{n})\$ is also easier to explain. You potentially iterate through \$m\$ rows and on each row, you do \$\log{n}\$ operations (the binary search). The simple product then is \$m\log{n}\$. Rewriting that as \$\log{n^m}\$ is true, but requires an extra step to justify. And I spent a whole paragraph on explaining why \$\mathcal{O}(mn\log{mn})\$ is \$\mathcal{O}(\log((mn)!))\$. So while \$\mathcal{O}(\log(n!))\$ is technically correct if \$n\$ is the total number of elements, \$\mathcal{O}(m\log{n})\$ (where \$n\$ is the number of columns) is generally a better description. It is less obfuscated and easier to understand.

Another issue is that I have no idea how you arrived at \$\mathcal{O}(\log(n!))\$. Even though it is correct, I'm not convinced that you know why it is correct. It can often be useful to give a short justification of your thinking, as I did with \$\mathcal{O}(m\log{n})\$. Because it makes a big difference whether you accidentally hit a correct value or if you performed the analysis correctly.

Often defining one's \$n\$ is an important part of complexity analysis. In this case, using it as the number of columns rather than the amount of data makes things simpler.