74. Search a 2D Matrix

You are given an m x n integer matrix matrix with the following two properties:

• Each row is sorted in non-decreasing order.

• The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in O(log(m * n)) time complexity.

Thoughts

• I think this should be as simple as performing a binary search on the last index of each row, and then binary searching within the correct row from there

  • This should cut down on the number of searches made and achieve O(log m*n)

  • yea just two consecutive while loops seems to be the play here

Solution

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int rowLow = 0, rowHigh = matrix.length - 1;
        int colLow = 0, colHigh = matrix[0].length - 1;
        int row = 0;

        // Binary search by the last element of the rows to find which row the target would be in
        while (rowLow <= rowHigh) {
            int rowMid = ((rowHigh - rowLow) / 2) + rowLow;
            if (matrix[rowMid][matrix[rowMid].length - 1] >= target) {
                if (matrix[rowMid][matrix[rowMid].length - 1] == target) {
                    return true;
                }
                row = rowMid;
            }

            if (matrix[rowMid][matrix[rowMid].length - 1] > target) {
                rowHigh = rowMid - 1;
            } else {
                rowLow = rowMid + 1;
            }
        }

        // Binary search within the rows to find (or not find) the target
        while (colLow <= colHigh) {
            int colMid = ((colHigh - colLow) / 2) + colLow;
            if (matrix[row][colMid] == target) {
                return true;
            }

            if (matrix[row][colMid] > target) {
                colHigh = colMid - 1;
            } else {
                colLow = colMid + 1;
            }
        } 

        return false;
    }
}

Time Complexity: O(log m * n)
Space Complexity: O(1)

Conclusion

This one was much easier since I had just reviewed my binary search knowledge by doing 704. Binary Search. This was much more fun and interesting than just a regular binary search problem. I felt like my brain was more stimulated by this than 704. Overall though, I definitely still need to brush up on my data structures and algorithms knowledge. I can feel some of my knowledge there slipping away and I really would like to prevent that from happening.