Problem overview
The function searchMatrix receives a matrix as an Array<IntArray>, one IntArray per row, and an integer target. It returns true if target appears anywhere 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 before it.
Take the matrix with rows [1, 3, 5, 7], [10, 11, 16, 20] and [23, 30, 34, 60]. For target = 3 the answer is true (row 0, column 1). For target = 13 it is false: 13 would sit between 11 and 16, but it isn't there. For target = 30 it is true.
The lesson asks for O(log(m · n)) time and O(1) extra space, where m is the number of rows and n the number of columns. Checking every cell costs O(m · n), so that is too slow.
Approach: treat the matrix as one sorted list
Read the rows one after another and you get a single sorted list. The second property is what guarantees it: each row ends below where the next one begins, so the values never go down. For the example matrix the list is 1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60, with positions 0 to 11.
A sorted list is exactly what binary search needs. The only obstacle is that the data isn't stored as one list. The fix is arithmetic: a position p in the imaginary list lives in row p / n and column p % n. Integer division counts the whole rows that come before p, and the remainder counts the cells already used in its own row. With 4 columns, position 9 is row 2, column 1, which holds 30.
No list is ever built, so the extra space is constant. Each pass of the search halves the range of positions, which gives the logarithmic time over m · n cells.
A common alternative is two searches: one over the first column to pick a row, then one inside that row. It works and is also logarithmic, but the single flat search needs only one loop and one set of bounds.
Step by step
- Measure the matrix.
mismatrix.size, the number of rows, andnis the size of the first row. Every row has the same length, so the first row is as good as any. - Set the search range over positions, not over cells:
leftstarts at 0 andrightatm * n - 1, the last position. Both arevars because the search moves them, and both ends are inclusive. - Loop while
left <= right. The comparison is<=because when the two are equal, one position is still unchecked. - Find the middle as
left + (right - left) / 2. Integer division rounds down, so the result is a valid position inside the range. - Convert the position to a cell with
middle / nfor the row andmiddle % nfor the column, and read the value there. - Found it? If the value equals
target, returntrueat once. - Value too small? Then
target, if present, is at a later position, so setlefttomiddle + 1. The value atmiddlehas been checked, so the new range excludes it. - Value too big? Set
righttomiddle - 1for the same reason. - Return
falseafter the loop. An empty range means every position that could hold the target was ruled out.
The solution in Kotlin
class Solution {
fun searchMatrix(matrix: Array<IntArray>, target: Int): Boolean {
val m = matrix.size
val n = matrix[0].size
var left = 0
var right = m * n - 1
while (left <= right) {
val middle = left + (right - left) / 2
val value = matrix[middle / n][middle % n]
if (value == target) {
return true
} else if (value < target) {
left = middle + 1
} else {
right = middle - 1
}
}
return false
}
}
Kotlin details worth a look:
- The matrix type.
Array<IntArray>is an array whose elements are primitiveintarrays.matrix[middle / n][middle % n]is a plain double index, andmatrix.sizeandmatrix[0].sizeread the two lengths. - Integer division.
/on twoInts truncates, somiddle / nis the row number with no rounding call.%gives the remainder, which is the column. - The midpoint formula.
(left + right) / 2can overflow anIntwhen both are large:(2_000_000_000 + 2_100_000_000) / 2gives-97483648, while2_000_000_000 + (2_100_000_000 - 2_000_000_000) / 2gives2050000000. With at most a million cells this can't happen here, but the habit is free and safe everywhere. valinside the loop.middleandvalueare new read-only variables on each pass, whileleftandrightarevars that live across passes.if/else ifchain. Each branch either returns or moves a bound, so every pass makes progress.
Complexity
Time: O(log(m · n)). The range holds m · n positions and each pass discards at least half of them. For a million cells that is about 20 passes. Converting a position to a cell takes constant time.
Space: O(1). The function keeps a handful of integers and never copies the matrix.
Edge cases and common mistakes
- A single cell. With a matrix of one row and one value,
leftandrightare both 0. The loop runs once, which is why the condition is<=. A matrix[[5]]returnstruefor 5 andfalsefor 4. - A single column. With
n = 1,middle / nis the position itself andmiddle % nis always 0, so the formula still works. The rows[1]and[3]with target 3 returntrue. - A single row. With
m = 1the search is an ordinary binary search on that row:[1, 3, 5]with target 3 returnstrue. - Targets outside the range. In the example matrix, 0 is below the smallest value and 61 above the largest, and both return
false. The first and last values, 1 and 60, returntrue. - Dividing by the wrong length. The row is
middle / n, withnthe number of columns. Usingmgives wrong cells, or an index out of bounds when the matrix isn't square. - Moving a bound to
middleinstead ofmiddle + 1ormiddle - 1. The range may then stop shrinking and the loop never ends. - Using
left < right. The last remaining position would never be checked.
Testing
Trace of target = 30 on the example matrix:
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=9 right=11 middle=10 row=2 col=2 value=34
left=9 right=9 middle=9 row=2 col=1 value=30
The first three values are compared and the range shrinks around position 9. On the fourth pass the value is 30, so the function returns true. Other inputs on the same matrix: target = 3 gives true, target = 13 gives false, target = 1 gives true, target = 60 gives true, and target = 0 gives false.
