Problem overview
The method searchMatrix receives an int[][] called matrix with m rows and n columns, plus an int called target. It returns true when target appears somewhere in the matrix and false otherwise.
The matrix has two properties. Every row is sorted in non-decreasing order, and the first value of each row is greater than the last value of the row above it. Take the matrix [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]]. Target 3 is in row 0, so the answer is true. Target 13 would sit between 11 and 16 in row 1 but is missing, so the answer is false. Target 30 is in row 2, column 1, so the answer is true.
The statement asks for O(log(m * n)) time and O(1) extra space. Checking every cell takes O(m * n), so that is too slow.
Approach: treat the matrix as one sorted list
The second property is the key. Because each row starts above the end of the previous row, reading the rows one after another gives a single list that never goes down. For the example it is 1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60: twelve values at positions 0 to 11.
A sorted list calls for binary search. The only problem is that the list does not exist in memory; the values live in rows. The fix is to do the search on positions and translate each position into a cell when you need its value. Every row holds n values, so position p lies after p / n complete rows and p % n cells of its own row:
- position 0 is row 0, column 0 (value 1);
- position 3 is row 0, column 3 (value 7);
- position 4 is row 1, column 0 (value 10);
- position 9 is row 2, column 1 (value 30).
Nothing is copied, so the extra space stays O(1). The search halves the range of positions each time, so it runs about log2(m * n) times. That is about 20 passes for a million cells.
Another common idea is to binary search the rows for the one that could hold the target and then binary search inside it. It also works and has the same complexity, but it needs two searches. The single search over positions is shorter.
Step by step
- Read the dimensions.
mismatrix.length, the number of rows.nismatrix[0].length, the length of the first row. All rows have the same length, so the first one is enough. - Set the range of positions.
leftstarts at 0 andrightatm * n - 1, the last position. Both ends are inclusive. - Loop while
left <= right. When the two are equal, one position is still unchecked, so the loop must run again. A strict<would skip it. - Pick the middle as
left + (right - left) / 2. Integer division rounds down, so no extra rounding is needed. - Turn the position into a cell. The row is
middle / nand the column ismiddle % n. Store that cell's value invalue. - Found it. If
valueequalstarget, returntrue. - Value too small. The target can only be at a later position, so
leftbecomesmiddle + 1. Usingmiddleitself would keep an already-checked position in the range, and the loop could repeat forever. - Value too big. The target can only be earlier, so
rightbecomesmiddle - 1. - Nothing left. When the loop ends, every position has been ruled out, so return
false.
The solution in Java
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
int left = 0, right = m * n - 1;
while (left <= right) {
int middle = left + (right - left) / 2;
int value = matrix[middle / n][middle % n];
if (value == target) {
return true;
} else if (value < target) {
left = middle + 1;
} else {
right = middle - 1;
}
}
return false;
}
}
A few details are worth a closer look:
int[][]is an array of rows.matrix.lengthcounts rows,matrix[0].lengthcounts columns, and a cell is read asmatrix[row][column]. Here the row comes first.- The midpoint formula.
left + (right - left) / 2never overflows, while(left + right) / 2can. Withleft = 2000000000andright = 2100000000, the sum wraps around and(left + right) / 2gives-97483648, whileleft + (right - left) / 2gives2050000000. Herem * nis at most a million, so either form is safe, but the safe one is a good habit. - Division and remainder. For non-negative ints,
/drops the fraction and%gives what is left over. That is exactly the row and column split. - Always
m * npositions. The constraints say every row hasnvalues, andnis at least 1, so readingmatrix[0]is safe.
Complexity
Time: O(log(m * n)). Each pass of the loop removes at least half of the positions still in the range, and the range starts with m * n positions.
Space: O(1). The method keeps a few ints and never builds a flat copy of the matrix.
Edge cases and common mistakes
- A single cell. For
[[1]], target 1 givestrueand target 2 givesfalse. Hereleftandrightare both 0, which is why the loop condition uses<=. - A single row or a single column.
[[1, 3]]with target 3 givestrue, and[[1], [3], [5]]with target 5 givestrue. In the column casenis 1, so the row is the position itself and the column is always 0. - Targets outside the range. In the example matrix, 0 is below the first value and 61 is above the last. Both return
false, because the range shrinks untilleftpassesright. - Mixing up
mandn. Dividing by the number of rows instead of the number of columns sends the search to wrong cells, and may read outside the matrix. Divide and take the remainder byn, the row length. - Moving to
middleinstead ofmiddle + 1ormiddle - 1. The range may stop shrinking, so the loop never ends.
Testing
For the example matrix, these calls give the following results:
- target 3 gives
true. - target 13 gives
false. - target 30 gives
true. - target 60, the last value, gives
true. - target 1, the first value, gives
true.
The search for 13 goes like this:
left=0 right=11 middle=5 value=11
left=6 right=11 middle=8 value=23
left=6 right=7 middle=6 value=16
left=6 right=5
Each value is compared with 13: 11 is smaller, so the search moves right; 23 and then 16 are bigger, so it moves left. The last line shows left past right, so the method returns false.
