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

Thinking

Rows and columns increase; find \(target\). A full scan is \(O(mn)\). Each row is sorted, so it admits binary search.

\(bisect\_left\) on every row returns on a hit. Column monotonicity is unused; the cost is \(O(m\log n)\).

The implementation walks rows and searches, in \(O(1)\) extra space, which is short when \(m\) is modest.

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
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        for (auto& row : matrix) {
            int j = lower_bound(row.begin(), row.end(), target) - row.begin();
            if (j < matrix[0].size() && row[j] == target) {
                return true;
            }
        }
        return false;
    }
};

1
2
3
4
5
6
7
8
9
func searchMatrix(matrix [][]int, target int) bool {
    for _, row := range matrix {
        j := sort.SearchInts(row, target)
        if j < len(matrix[0]) && row[j] == target {
            return true
        }
    }
    return false
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
function searchMatrix(matrix: number[][], target: number): boolean {
    const n = matrix[0].length;
    for (const row of matrix) {
        let left = 0,
            right = n;
        while (left < right) {
            const mid = (left + right) >> 1;
            if (row[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        if (left != n && row[left] == target) {
            return true;
        }
    }
    return false;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
use std::cmp::Ordering;

impl Solution {
    pub fn search_matrix(matrix: Vec<Vec<i32>>, target: i32) -> bool {
        let m = matrix.len();
        let n = matrix[0].len();
        let mut i = 0;
        let mut j = n;
        while i < m && j > 0 {
            match target.cmp(&matrix[i][j - 1]) {
                Ordering::Less => {
                    j -= 1;
                }
                Ordering::Greater => {
                    i += 1;
                }
                Ordering::Equal => {
                    return true;
                }
            }
        }
        false
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function (matrix, target) {
    const n = matrix[0].length;
    for (const row of matrix) {
        let left = 0,
            right = n;
        while (left < right) {
            const mid = (left + right) >> 1;
            if (row[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        if (left != n && row[left] == target) {
            return true;
        }
    }
    return false;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
public class Solution {
    public bool SearchMatrix(int[][] matrix, int target) {
        foreach (int[] row in matrix) {
            int j = Array.BinarySearch(row, target);
            if (j >= 0) {
                return true;
            }
        }
        return false;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
        for row in matrix {
            if binarySearch(row, target) {
                return true
            }
        }
        return false
    }

    private func binarySearch(_ array: [Int], _ target: Int) -> Bool {
        var left = 0
        var right = array.count - 1

        while left <= right {
            let mid = left + (right - left) / 2
            if array[mid] == target {
                return true
            } else if array[mid] < target {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }

        return false
    }
}

Solution 2: Search from the Bottom Left or Top Right

Thinking

Solution 1 ignores increasing columns and may inspect every row.

From the bottom-left (or top-right): a too-large value moves up and drops that column’s larger suffix; a too-small value moves right and drops that row’s smaller prefix. Each step deletes a row or a column, in \(O(m+n)\).

Here, we start searching from the bottom left corner and move towards the top right direction, comparing the current element matrix[i][j] with target:

  • If \(\textit{matrix}[i][j] = \textit{target}\), it means the target value has been found, and we directly return true.
  • If \(\textit{matrix}[i][j] > \textit{target}\), it means all elements in this column from the current position upwards are greater than target, so we should move the \(i\) pointer upwards, i.e., \(i \leftarrow i - 1\).
  • If \(\textit{matrix}[i][j] < \textit{target}\), it means all elements in this row from the current position to the right are less than target, so we should move the \(j\) pointer to the right, i.e., \(j \leftarrow j + 1\).

If the search ends and the target is still not found, return false.

The time complexity is \(O(m + 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
 8
 9
10
11
12
13
14
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix:
            return False
        m, n = len(matrix), len(matrix[0])
        i, j = m - 1, 0
        while i >= 0 and j < n:
            if matrix[i][j] == target:
                return True
            if matrix[i][j] > target:
                i -= 1
            else:
                j += 1
        return False

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) {
            return false;
        }
        int m = matrix.length, n = matrix[0].length;
        int i = m - 1, j = 0;
        while (i >= 0 && j < n) {
            if (matrix[i][j] == target) {
                return true;
            }
            if (matrix[i][j] > target) {
                --i;
            } else {
                ++j;
            }
        }
        return false;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty()) {
            return false;
        }
        int m = matrix.size(), n = matrix[0].size();
        int i = m - 1, j = 0;
        while (i >= 0 && j < n) {
            if (matrix[i][j] == target) {
                return true;
            }
            if (matrix[i][j] > target) {
                --i;
            } else {
                ++j;
            }
        }
        return false;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
func searchMatrix(matrix [][]int, target int) bool {
    if len(matrix) == 0 {
        return false
    }
    m, n := len(matrix), len(matrix[0])
    i, j := m-1, 0
    for i >= 0 && j < n {
        if matrix[i][j] == target {
            return true
        }
        if matrix[i][j] > target {
            i--
        } else {
            j++
        }
    }
    return false
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
function searchMatrix(matrix: number[][], target: number): boolean {
    if (matrix.length === 0) {
        return false;
    }
    const [m, n] = [matrix.length, matrix[0].length];
    let [i, j] = [m - 1, 0];
    while (i >= 0 && j < n) {
        if (matrix[i][j] === target) {
            return true;
        }
        if (matrix[i][j] > target) {
            --i;
        } else {
            ++j;
        }
    }
    return false;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public bool SearchMatrix(int[][] matrix, int target) {
        if (matrix.Length == 0) {
            return false;
        }
        int m = matrix.Length, n = matrix[0].Length;
        int i = m - 1, j = 0;
        while (i >= 0 && j < n) {
            if (matrix[i][j] == target) {
                return true;
            }
            if (matrix[i][j] > target) {
                --i;
            } else {
                ++j;
            }
        }
        return false;
    }
}

Comments