Search a 2D Matrix II
Medium · Binary Search · Array · Binary Search · Divide and Conquer · Matrix
Problem
You are given an m x n matrix of integers in which every row is sorted in ascending order from left to right and every column is sorted in ascending order from top to bottom. Unlike a fully sorted matrix, a row may start with a value smaller than the end of the row above it.
Given target, return true if it appears in the matrix, and false otherwise. Aim to do better than looking at every cell.
Examples
Input: matrix = [[1,5,9],[3,6,12],[8,10,14]], target = 10 Output: true
From 9 at the top-right: 9 10, step left to 6; 6 < 10, step down to 10.
Input: matrix = [[1,5,9],[3,6,12],[8,10,14]], target = 7 Output: false
The walk goes 9, 5, 6, 10, 8 and then off the left edge without meeting 7.
Input: matrix = [[1,5,9],[3,6,12],[8,10,14]], target = 3 Output: true
Row 1 starts at 3, below the 9 that ends row 0: the rows overlap, but the walk still finds it.
Constraints
- m == len(matrix), n == len(matrix[i])
- 1 <= m, n <= 300
- -10^9 <= matrix[i][j], target <= 10^9
- every row and every column is sorted in ascending order
Approaches
- Baseline: binary search every row — time O(m log n), space O(1)
Follow-up
The same staircase counts how many values are at most x in O(m + n). With that count, the k-th smallest value can be found by binary searching on the value range, which is the usual way to answer order-statistic questions on such a matrix.
Related problems
Start free on Cariara · Coding problems · System design studio
