Search a matrix sorted in reading order
An m × n matrix of integers has two properties: each row is sorted in increasing order,
and the first value of each row is greater than the last value of the row above. Return true if
target is in the matrix and false otherwise, in O(log(m × n)) time.
Examples
| Input | Output | Why |
|---|---|---|
matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 | true | |
matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 | false |
Constraints
- 1 ≤ m, n ≤ 100
- −10⁴ ≤ matrix[i][j], target ≤ 10⁴
Hints
Hint 1
Write the matrix out row after row. What do you get?
Hint 2
A sorted list of m × n values. Position k in that list is row k / n, column k % n.
Hint 3
Run the exact-match search over k in [0, m × n − 1], reading matrix[k / n][k % n] at each step.
Where people lose marks
- Dividing by the number of rows instead of the number of columns.
- Using this method on a matrix whose rows and columns are sorted but whose rows overlap: reading order is then not sorted. That is the next problem.
Dry run on [[2,4,7,9],[12,15,18,21],[25,28,33,40]],28
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 5lo0hi11
Positions 0 to 11 in reading order. Position k is row ⌊k / 4⌋, column k mod 4.
-
Step 2 / 5lo0mid5hi11row1col1
Position 5 is row 5 / 4 = 1, column 5 mod 4 = 1, holding 15. 15 < 28: lo = 6.
-
Step 3 / 5lo6mid8hi11row2col0
Position 8 is row 8 / 4 = 2, column 8 mod 4 = 0, holding 25. 25 < 28: lo = 9.
-
Step 4 / 5lo9mid10hi11row2col2
Position 10 is row 10 / 4 = 2, column 10 mod 4 = 2, holding 33. 33 > 28: hi = 9.
-
Step 5 / 5mid9row2col1
Position 9 is (2, 1), which holds 28: found.
How to think about it
The two properties together say that reading the matrix row by row, left to right, gives a sorted
sequence. So the matrix is a sorted array of length m × n, stored in rows. There is no need to copy
it: position k of that array is
row = k / n, col = k % n (integer division).
Run the ordinary exact search over k ∈ [0, mn − 1] and translate each mid into a
cell. The cost is O(log(mn)) = O(log m + log n), the same as searching for the row first and then the column,
with one loop instead of two.
The two-search version, first the last row whose first value is ≤ target and then the row itself, is also correct and is a fine answer. The single search is shorter and has one fewer boundary to get wrong.
Complexity. Time O(log(m·n)) · Space O(1)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def search_matrix(matrix, target):
m, n = len(matrix), len(matrix[0])
lo, hi = 0, m * n - 1 # positions in reading order
while lo <= hi:
mid = (lo + hi) // 2
v = matrix[mid // n][mid % n] # row = mid // n, col = mid % n
if v == target:
return True
if v < target:
lo = mid + 1
else:
hi = mid - 1
return False#include <vector>
bool solve(const std::vector<std::vector<int>>& matrix, int target) {
const int m = (int)matrix.size(), n = (int)matrix[0].size();
int lo = 0, hi = m * n - 1; // positions in reading order
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
int v = matrix[mid / n][mid % n];
if (v == target) return true;
if (v < target) lo = mid + 1; else hi = mid - 1;
}
return false;
}class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
int lo = 0, hi = m * n - 1; // positions in reading order
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
int v = matrix[mid / n][mid % n];
if (v == target) return true;
if (v < target) lo = mid + 1; else hi = mid - 1;
}
return false;
}
}function searchMatrix(matrix, target) {
const m = matrix.length, n = matrix[0].length;
let lo = 0, hi = m * n - 1; // positions in reading order
while (lo <= hi) {
const mid = (lo + hi) >> 1;
const v = matrix[Math.floor(mid / n)][mid % n];
if (v === target) return true;
if (v < target) lo = mid + 1; else hi = mid - 1;
}
return false;
}fn solve<const C: usize>(matrix: &[[i64; C]], target: i64) -> bool {
let (m, n) = (matrix.len(), C);
let (mut lo, mut hi) = (0usize, m * n); // half-open: positions in [lo, hi)
while lo < hi {
let mid = lo + (hi - lo) / 2;
let v = matrix[mid / n][mid % n];
if v == target {
return true;
}
if v < target { lo = mid + 1 } else { hi = mid }
}
false
}import Data.Array
solve :: [[Int]] -> Int -> Bool
solve rows target = go 0 (m * n - 1)
where
m = length rows
n = length (head rows)
a = listArray (0, m * n - 1) (concat rows) -- reading order; lists have no O(1) indexing
go lo hi
| lo > hi = False
| v == target = True
| v < target = go (mid + 1) hi
| otherwise = go lo (mid - 1)
where
mid = lo + (hi - lo) `div` 2
v = a ! midVariants to try
- Rows and columns each sorted, rows overlapping: start at the top-right corner and walk.
- Count the values less than target: the lower bound of target in the same index space.
Next problems
Search a matrix sorted along rows and columns
From the top-right corner, one comparison rules out a whole row or a whole column. m + n steps, and why plain binary search does worse.
Open the problem → Easy10 minFind a value in a sorted array
The search every other binary search is built on: halve a closed range until the value is found or the range is empty.
Open the problem → Easy10 minInteger square root without a library
Search the candidates 0 to n for the last x with x² ≤ n, and keep the square from overflowing.
Open the problem →Write a solution and run it against the real test table.
Keep going
Search a matrix sorted along rows and columns
From the top-right corner, one comparison rules out a whole row or a whole column. m + n steps, and why plain binary search does worse.
Open the problem → Easy10 minFind a value in a sorted array
The search every other binary search is built on: halve a closed range until the value is found or the range is empty.
Open the problem → Easy10 minInteger square root without a library
Search the candidates 0 to n for the last x with x² ≤ n, and keep the square from overflowing.
Open the problem → Binary searchThe pattern behind it
Search the answer, not the array: halve a monotone predicate until one candidate is left.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.