Problem overview
searchMatrix receives a matrix as an array of rows, [[Int]], and a number target. It returns true when the target appears somewhere in the matrix and false otherwise. Two properties are guaranteed: every row is sorted in non-decreasing order, and each row starts with a value greater than the last value of the row above it.
Take this matrix:
[1, 3, 5, 7]
[10, 11, 16, 20]
[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, and it isn't there. With target = 30 it is true (row 2, column 1).
The task 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 cost O(m · n).
Approach: one sorted list in disguise
The two properties together say something simple: if you read the matrix row by row, the 12 values form a single sorted list.
1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60
Binary search works on any sorted sequence, so it can run on the positions 0 to m * n - 1 of that imaginary list. The matrix is never copied into a list. Instead, each position is converted back to a cell with arithmetic:
- the row is
position / n, the number of whole rows before that position; - the column is
position % n, how far into its own row it sits.
With 4 columns, position 9 is row 9 / 4 = 2 and column 9 % 4 = 1, which is the 30 in the example. Because nothing is built, the extra space stays constant, and because every step halves the range of positions, the time is logarithmic in m · n. For a million cells that means about 20 steps.
Step by step
- Read the shape.
mismatrix.count, the number of rows.nis the length of the first row, which equals the length of every row. - Set the search range over positions with two
vars:leftstarts at 0 andrightatm * n - 1. Both ends are inclusive, and they are variables because the search moves them. - Loop while
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 already rounds down, and adding half the distance toleftgives the same position as halvingleft + rightwithout a sum that could grow too large. - Turn the position into a cell with
middle / nandmiddle % n, and read its value from the matrix. - Found it: if the value equals the target, return
true. - Value too small: the target can only be at a later position, so move
lefttomiddle + 1. Usingmiddle + 1rather thanmiddlematters, because the value atmiddlewas already checked, and keeping it in the range could make the loop run forever. - Value too big: move
righttomiddle - 1. - Range empty: after the loop, every position that could hold the target has been ruled out, so return
false.
The solution in Swift
class Solution {
func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
let m = matrix.count, n = matrix[0].count
var left = 0, right = m * n - 1
while left <= right {
let middle = left + (right - left) / 2
let 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 Swift details:
- Two constants in one line.
let m = matrix.count, n = matrix[0].countdeclares twoletconstants at once. The same works withvarforleftandright. - Nested indexing.
matrix[middle / n][middle % n]first picks a row, which is an[Int], then an element of it. Swift checks array indexes at run time, so an index outside the array stops the program instead of reading stray memory. - Integer division and
%. Both operands areInt, so/drops the fraction:9 / 4is 2 and9 % 4is 1. The positions are never negative here, so truncation toward zero and rounding down are the same thing. - 64-bit
Int.m * nis at most a million in this lesson, far below the 64-bit limit. In Swift anIntoverflow stops the program rather than wrapping, but that can't happen with these sizes. - Arguments without labels. The
_beforematrixandtargetmeans the caller writessearchMatrix(grid, 3)without labels.
Complexity
Time: O(log(m · n)). The range holds m * n positions at the start and loses about half of them on every pass, so the loop runs at most about log2(m · n) times. Each pass does a constant amount of work: one division, one remainder and two array reads.
Space: O(1). The code keeps a handful of integers. The imaginary sorted list is never created.
Edge cases and common mistakes
- A single cell. For
[[5]],leftandrightboth start at 0. The loop runs once, so a target of 5 givestrueand a target of 4 givesfalse. This is where<=matters. - One column or one row. With
[[1], [3], [5]],nis 1, somiddle / nis the position itself andmiddle % nis 0. With[[1, 2, 3]],middle / nis always 0. The same formulas cover both. - Dividing by the wrong size. The row is
middle / n(the number of columns), notmiddle / m. With the example matrix, usingm = 3would map position 9 to row 3, which doesn't exist. - Targets outside the range. A target below the first value or above the last one ends with
falseafter the range shrinks to nothing. For the example, 0 and 61 both givefalse. left = middleorright = middle. Without the+ 1and- 1, a range of two positions can stay the same size forever.- Searching row by row. Scanning every row is
O(m · n). Picking the right row first and then searching it also works, but the single search over positions is shorter.
Testing
On the example matrix above, the solution returns:
target = 3givestrue.target = 13givesfalse.target = 30givestrue.target = 1givestrue, andtarget = 60givestrue: the first and last cells.target = 0givesfalse, andtarget = 61givesfalse.
For target = 30 the search visits positions 5 (value 11), 8 (23), 10 (34) and 9 (30), then returns true. For target = 13 it visits positions 5 (11), 8 (23) and 6 (16), then the range is empty and the result is false.
Other inputs: [[5]] with 5 gives true, [[5]] with 4 gives false, [[1], [3], [5]] with 3 gives true, and [[1, 2, 3]] with 2 gives true.
