Pattern visualizer
Search a 2D Matrix
Each row's smallest value exceeds the previous row's largest value, so reading the matrix row by row, left to right, produces one fully sorted sequence. That means there's no need for a 2D search at all — plain binary search over the flattened array finds the target in O(log(rows*cols)). Animated on: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 (shown flattened row-major into a 12-cell sorted array)..
Treat it as one sorted array
time O(log(rows * cols))space O(1)step 1 / 9
1
[0]3
[1]5
[2]7
[3]10
[4]11
[5]16
[6]20
[7]23
[8]30
[9]34
[10]60
[11]line 3
Each row's values exceed the previous row's, so the flattened matrix is fully sorted — binary search works directly. target=3.
Pseudocode
1FUNCTION searchMatrix(matrix, target):2 flat = read the matrix row by row into one list (already sorted, since each row's values exceed the previous row's)3 low = 0, high = the length of flat - 14 WHILE low <= high:5 mid = (low + high) / 2, rounded down6 IF flat[mid] equals target: RETURN true7 ELSE IF flat[mid] > target: high = mid - 18 ELSE: low = mid + 19 RETURN false
← / → step · space play · Home restart