Search a 2D Matrix

NeetCode: Search a 2D Matrix · LeetCode: 74. Search a 2D Matrix · Difficulty: Medium

A matrix has rows sorted left to right, and the first number of each row is greater than the last number of the previous row. Return true if target is in the matrix. The solution must run in O(log(m·n)).

Example

Text

Input:  matrix = [[1, 2, 4, 8], [10, 11, 12, 13], [14, 20, 30, 40]], target = 10    Output: true
Input:  the same matrix, target = 15                                                Output: false

Brute force: check every cell

Walk every row and every column and compare with the target.

Java

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        for (int[] row : matrix) {
            for (int value : row) {
                if (value == target) {
                    return true;
                }
            }
        }
        return false;
    }
}

public class Main {
    public static void main(String[] args) {
        int[][] m = {{1, 2, 4, 8}, {10, 11, 12, 13}, {14, 20, 30, 40}};
        Solution s = new Solution();
        System.out.println(s.searchMatrix(m, 10));
        System.out.println(s.searchMatrix(m, 15));
    }
}

Output

true
false

Time: O(m · n). Space: O(1).

Optimal: binary search as if it were one long array

Because each row continues where the previous one ends, the matrix read row by row is a single sorted array of m * n numbers. Binary search over the index 0..m*n and translate the middle index back to a cell with row = mid / n, col = mid % n. In Java a 2D array is an array of row arrays, so matrix[row][col] reads one cell. LeetCode guarantees at least one row and one column, and m * n fits in an int under its constraints (at most 100 by 100).

Java

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        int lo = 0;
        int hi = rows * cols; // half-open range [lo, hi)
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            int value = matrix[mid / cols][mid % cols];
            if (value == target) {
                return true;
            } else if (value < target) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return false;
    }
}

public class Main {
    public static void main(String[] args) {
        int[][] m = {{1, 2, 4, 8}, {10, 11, 12, 13}, {14, 20, 30, 40}};
        Solution s = new Solution();
        System.out.println(s.searchMatrix(m, 10));
        System.out.println(s.searchMatrix(m, 15));
        System.out.println(s.searchMatrix(new int[][] {{5}}, 5));
        System.out.println(s.searchMatrix(m, 40));
    }
}

Output

true
false
true
true

Time: O(log(m · n)). Space: O(1).