Skip to content

10.09. Sorted Matrix Search

Description

Given an M x N matrix in which each row and each column is sorted in ascending order, write a method to find an element.

Example:

Given 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]

]

Given target = 5, return true.

Given target = 20, return false.

Solutions

Since all elements in each row are sorted in ascending order, we can use binary search to find the first element that is greater than or equal to target for each row, and then check if this element is equal to target. If it equals target, it means the target value has been found, and we directly return true. If it does not equal target, it means all elements in this row are less than target, and we should continue to search the next row.

If all rows have been searched and the target value has not been found, it means the target value does not exist, so we return false.

The time complexity is $O(m \times \log n)$, where $m$ and $n$ are the number of rows and columns in the matrix, respectively. The space complexity is $O(1)$.

1
2
3
4
5
6
7
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        for row in matrix:
            j = bisect_left(row, target)
            if j < len(matrix[0]) and row[j] == target:
                return True
        return False

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        for (var row : matrix) {
            int j = Arrays.binarySearch(row, target);
            if (j >= 0) {
                return true;
            }
        }
        return false;
    }
}

 1