Leetcode — 240. Search a 2D Matrix II

The link to the problem: https://leetcode.com/problems/search-a-2d-matrix-ii/

Write an efficient algorithm that searches for a target value in an m x n integer matrix. The 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.

Example
Input: matrix = [[ 1, 4, 7,11,15],
                 [ 2, 5, 8,12,19],
                 [ 3, 6, 9,16,22],
                 [10,13,14,17,24],
                 [18,21,23,26,30]], target = 5
Output: true

Thoughts:

The idea of how we solve this problem is different than the idea of solving 74. Search a 2D Matrix since the array conditions are totally different. In problem 74, the matrix is only sorted in each row but not sorted in each column. Also, the matrix in problem 74 is guaranteed that the end of the current row is always less than equal to the first cell of the next row. Hence, we can relabel all the cells according to their row number and column number and treat the 2D array as a sorted 1D array. Hence, we can use binary search and spend O(lg(m*n)) to solve the problem.

The 0ms code of problem 74 will be something like below:

public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        if(matrix[0][0]>target || matrix[m-1][n-1]<target)
            return false;
        //if consider a 1D array, each num is at: n*i+j
        int s = 0, e = n*m-1;
        while(s<=e)
        {
            int mid = s + (e-s)/2; 
            int i = mid/n; 
            int j = mid%n;
            if(matrix[i][j]==target)
                return true;
            if(matrix[i][j]<target)
                s = mid+1;
            else 
                e = mid-1;
        }
        return false;
    }

However, the given matrix in this problem is sorted in each row and each column. We can’t just simply merge all the rows together and treat them as a whole 1D array. I mean, yes you can still merge it as a 1D array. However, this merged 1D array will not be sorted and we of course cannot use binary search on an unsorted array. We need to spend some time sorting before we can use O(lg(m*n)) to search the target.

Hence, we need to make use of the fact that “elements in each row and each column are sorted”. Also, the number of the current position matrix[i][j] will be smaller than its right cell matrix[i][j+1] and the cell below matrix[i+1][j].

My first idea is that we are going to traverse from the top left (0,0). If the target is smaller than the current position number, we will just return false, since it is impossible to find a smaller number if we keep going down or right. If the target is bigger than the current number, we will need to split the path to heading right AND heading down to check whether we will find the target in either path. Since we really don’t know where we will find the target in both paths, we will need to keep splitting our paths until we found the target in one of the paths OR until we check every path and didn’t find the target.

Below is the code that will pass 124/128 cases on Leetcode, but failed due to Time Limit Exceeded:

public boolean searchMatrix(int[][] matrix, int target) {
        return helper(matrix,0,0,target);
    }
    public boolean helper(int[][] arr,int i,int j, int target){
        if(i>=arr.length||j>=arr[i].length||arr[i][j]>target)
            return false;
        if(arr[i][j]==target)
            return true;
        return helper(arr,i+1,j,target)||helper(arr,i,j+1,target);
    }

We can see that we only stop forwarding some path only when the target is smaller than the number. It is also highly possible that we traverse a path more than one time. For example, we might traverse the path from (1,1) twice since the previous cell/step is (0,1) and (1,0). We will hence traverse the cells on this path more than twice and more and more.
Is there any way that we avoid traversing duplicated cells and at most traverse a cell once?

Code Logic:

We should find a way that if we are in the current position, we will either going direction A or direction B depends on the value. i.e., we need to change our mind about traverse the whole array from the top-left since we will always need to go left AND down if the condition is met.

If we traverse from the bottom-right, then the result is the same, we will always need to go up AND left if the condition is met. However, if we traverse the matrix from bottom-left OR top-right, we will only need to head in one direction if the condition is met.

You can just choose whatever you like. I will just choose to traverse the matrix from the bottom-left and let’s see what’s the difference if we make this change. 👉

You might be wondering, what’s special about the bottom-left matrix[n-1][0]?

Since it is on the bottom row, there are no larger elements on the cells below; and since it is on the leftmost column, there are no smaller elements on the left. To sum up, if we want to find a larger number, we just need to go to our right; if we want to find a smaller number, we just need to go upward. (vice versa if we set our starting point at the top-right cell)

Hence, this only requires O(m+n) time complexity since we always either move one row or one column at a time in each iteration.

Below is the 5ms code that beats 47% —

public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        return helper(matrix,m-1,0,target);
    }
    public boolean helper(int[][] arr,int i,int j, int target){
        if(i<0||j<0||i>=arr.length||j>=arr[i].length)
            return false;
        if(arr[i][j]==target)
            return true;
        if(arr[i][j]<target)
            return helper(arr,i,j+1,target);
        else
            return helper(arr,i-1,j,target);
    }

Or if we do it iteratively, we can get the below 4ms code that beats 99% —

public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int i = m-1, j = 0;
        while(i>=0 && j>=0 && i<m && j<n)
        {
            if(matrix[i][j]==target)
                return true;
            if(matrix[i][j]>target)
                i--;
            else
                j++;
        }
        return false;
    }

Time Complexity: O(m+n)
Space Complexity: O(1)