Problem overview
The function searchMatrix receives a vector<vector<int>> named matrix and an int named 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 with rows {1, 3, 5, 7}, {10, 11, 16, 20} and {23, 30, 34, 60}. With target = 3 the answer is true (row 0, column 1). With target = 13 it is false: 13 would sit between 11 and 16 in row 1, and it isn't there. With target = 30 it is true (row 2, column 1).
The statement asks for O(log(m · n)) time and O(1) extra space, where the matrix has m rows and n columns. Checking every cell would take O(m · n).
Approach: one sorted list in disguise
The two properties together mean something simple: read the matrix row by row and the values never go down. The matrix is one sorted list of m * n values, only folded into rows. Sorted data calls for binary search, and the search can run on positions 0 to m * n - 1 of that imaginary list.
The list doesn't exist in memory, and building it would cost O(m · n) time and space. Instead, the search converts a position into a cell when it needs a value. Every row holds n values, so the positions before position p fill p / n whole rows and p % n cells of the next one. Position p is therefore in row p / n, column p % n. With 4 columns, position 9 is row 2, column 1, which is where the 30 sits.
Each pass compares the middle value with the target and throws away half of the remaining positions. A million cells need about 20 passes.
Here is the search for target = 13 in the matrix above, as the lesson's code runs it:
left=0 right=11 middle=5 row=1 col=1 value=11
left=6 right=11 middle=8 row=2 col=0 value=23
left=6 right=7 middle=6 row=1 col=2 value=16
11 is too small, so the search moves right of position 5. 23 is too big, so it moves left of position 8. 16 is too big too, so the range becomes empty and the function returns false. For target = 30 the middle positions are 5, 8, 10 and 9, and position 9 holds 30.
Step by step
- Read the dimensions.
mismatrix.size()andnis the size of the first row. Every row has the same length, so the first row is enough. - Set the search range to positions
left = 0throughright = m * n - 1. Both ends are inclusive:rightis the last position itself. - Loop while the range is not empty, which is
left <= right. When the two are equal, one position is still unchecked, so a strict<would skip it. - Pick the middle as
left + (right - left) / 2. Integer division rounds down here, and adding half the distance toleftgives the same position as(left + right) / 2without ever forming a sum that could overflow. - Turn the position into a cell with
middle / nandmiddle % n, and read the value there. - Equal to the target: return
true. - Smaller than the target: the target can only be later, so set
lefttomiddle + 1. - Bigger than the target: set
righttomiddle - 1. - After the loop every position has been ruled out, so return
false.
The solution in C++
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size(), n = matrix[0].size();
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;
}
};
The C++ details worth a closer look:
- Taking the matrix by reference. The
&invector<vector<int>>& matrixmeans the function reads the caller's matrix instead of copying up to a million values. size()returns an unsigned type. Storing it in anintis fine here because the constraints keep the sizes at 1000 or less. The function does no subtraction on the sizes, so there is no unsigned wrap-around.- The product
m * nis at most 1,000,000, far inside theintrange. Signed overflow in C++ is undefined behaviour, so a product that could exceed the range would call forlong long. - Two indexes, no copies.
matrix[middle / n][middle % n]first picks a row (a reference to avector<int>), then a cell of it. Nothing is built, so the extra space staysO(1). - Zero rows.
matrix[0]is only safe on a non-empty matrix, which the constraints guarantee.
Complexity
Time: O(log(m · n)). Each pass halves the range of positions, which starts at m * n, so the loop runs at most about log2(m · n) times. Each pass does a constant amount of work: one division, one remainder and one comparison.
Space: O(1). The function keeps a handful of int variables, however big the matrix is.
Edge cases and common mistakes
- A single cell. For
{{5}}the range is just position 0. Target 5 returnstrueand target 4 returnsfalse. - One row or one column. For
{{1, 3, 5, 7, 9}}every position is in row 0, and for{{1}, {3}, {5}}nis 1, so every position is in column 0. The same formulas work for both. - Targets outside the range. In the example matrix, 61 and 0 both return
false: the search keeps moving one way until the range empties. - Dividing by the wrong size. Using
minstead ofninmiddle / nandmiddle % nmaps positions to the wrong cells, and can read outside the matrix when the matrix isn't square. The divisor is the number of columns. - Using
left < right. The last remaining position is then never checked. - Setting
left = middleorright = middle. The value atmiddlehas already been checked, and keeping it in the range can make the loop run forever whenleftandrightare neighbours. - Searching row by row. A binary search in every row costs
O(m log n), which is more than the single search over all positions.
Testing
- The example matrix with
target = 3givestrue, with13givesfalse, and with30givestrue. - The example matrix with
target = 61ortarget = 0givesfalse. {{5}}withtarget = 5givestrue, and withtarget = 4givesfalse.{{1, 3, 5, 7, 9}}withtarget = 9givestrue, and withtarget = 2givesfalse.{{1}, {3}, {5}}withtarget = 5givestrue, with4givesfalse, and with1givestrue.
