Binary Search on Matrix

74. Search a 2D Matrix

To determine which row to search, you can check the last element of each row. This can be achieved by using binary search. Then binary search in that row to find the element.

    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int m = matrix.length, n = matrix[0].length;
        int row = findRow(matrix, target, 0, m - 1);
        int left = 0, right = n - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (matrix[row][mid] == target) {
                return true;
            } else if (matrix[row][mid] < target) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return matrix[row][left] == target || matrix[row][right] == target;
    }
    
    private int findRow(int[][] matrix, int target, int top, int bottom) {
        int last = matrix[0].length - 1;
        while (top + 1 < bottom) {
            int mid = top + (bottom - top) / 2;
            if (matrix[mid][last] >= target) {
                bottom = mid;
            } else {
                top = mid;
            }
        }
        if (target <= matrix[top][last]) {
            return top;
        }
        return bottom;
    }

240. Search a 2D Matrix II

1. BFS, starting from top left node, traverse to right and down direction on each node, until find the target.

T: O(m *n) S: O(m*n) TLE

    int[][] dirs = {{0,1}, {1,0}};
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0});
        while (!queue.isEmpty()) {
            int[] curt = queue.poll();
            if (matrix[curt[0]][curt[1]] > target) continue;
            if (matrix[curt[0]][curt[1]] == target) {
                return true;
            }
            for (int[] dir : dirs) {
                int newx = dir[0] + curt[0];
                int newy = dir[1] + curt[1];
                if (newx < matrix.length && newy < matrix[0].length) {
                    queue.offer(new int[]{newx, newy});
                }
            }
        }
        return false;
    }

2. Divide and Conquer, Divide the matrix into 4 subregion:

  zone 1      zone 2
*  *  *  * | *  *  *  *
*  *  *  * | *  *  *  *
*  *  *  * | *  *  *  *
*  *  *  * | *  *  *  *
-----------------------
*  *  *  * | *  *  *  *
*  *  *  * | *  *  *  *
*  *  *  * | *  *  *  *
*  *  *  * | *  *  *  *
  zone 3      zone 4

• matrix[mid_row][mid_col] == target: return true

• matrix[mid_row][mid_col] > target: search in region 1,2,3

• matrix[mid_row][mid_col] < target: search in region 2,3,4

T: O((MN)log4(3)) because the recursive equation of this solution is T(n) = 3T(n/4) + O(1).

It reduces the problem by 3/4 every function call. The base case would be a 1 x 1 matrix. So

mn * (3/4)^x = 1,

thus we have x = log(3/4, 1/mn) = log(4/3, mn) $a = b$

Thus,

T(m * n) = O(lg(mn)) = O(lg(m) + lg(n))

    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
        if(matrix.length == 1 && matrix[0].length == 1) return matrix[0][0] == target;
        return search(matrix, 0, matrix.length - 1, 0, matrix[0].length - 1, target);
    }
    
    private boolean search(int[][] matrix, int sRow, int eRow, int sCol, int eCol, int target) {
        if (sRow > eRow || sCol > eCol) return false;
        if (sRow == eRow && sCol == eCol) return matrix[sRow][sCol] == target;
        int mRow = (sRow + eRow) / 2;
        int mCol = (sCol + eCol) / 2;
        if (matrix[mRow][mCol] == target) {
            return true;
        } else if (matrix[mRow][mCol] > target) { // search 1,2,3
            return search(matrix, sRow, mRow, sCol, mCol, target) 
                || search(matrix, mRow + 1, eRow, sCol, mCol, target)
                || search(matrix, sRow, mRow, mCol + 1, eCol, target) ;
        } else { // search 2,3,4
            return search(matrix, mRow + 1, eRow, mCol + 1, eCol, target)
                || search(matrix, mRow + 1, eRow, sCol, mCol, target)
                || search(matrix, sRow, mRow, mCol + 1, eCol, target) ;
        }
    }

3. Search Space Reduction

Starts from top-right element, move down if matrix[row][col] < target, move left if matrix[row][col] > target.

T: O(m + n)

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

378. Kth Smallest Element in a Sorted Matrix

Binary Search between the max and min elements in the matrix. The min is the top-left element, max is the bottom-right element. Each search, take the mid as a threshold, and count how many elements are smaller than the threshold.

T: O(N * log(max - min)) S: O(1)

    public int kthSmallest(int[][] matrix, int k) {
        int m = matrix.length, n = matrix[0].length;
        int left = matrix[0][0], right = matrix[m - 1][n - 1];
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (hasSmaller(matrix, mid) < k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
    
    private int hasSmaller(int[][] matrix, int x) {
        int count = 0;
        for (int[] row : matrix) {
            int n = matrix[0].length;
            if (row[n - 1] <= x) {
                count += row.length;   
            } else {
                for (int i = 0; i < n && row[i] <= x; i++) {
                    count++;
                }
            } 
        }
        return count;
    }