Sorted matrices

Lesson · 9 min read · Binary search · Sorted matrices

Two kinds of sorted matrix ask for two different searches. In reading order it is one long array; sorted by rows and columns it is a walk from a corner.

Sorted in reading order

When each row is sorted and every row starts above where the previous one ended, reading the matrix row by row gives one sorted list of m × n values. Search that list without building it: position k is row k / n, column k mod n.

Position 6 in reading order is row 6 / 4 = 1, column 6 mod 4 = 2: the value 20.

Looking for 20 with one binary search over the 12 positions.

Step 1 / 4

lo0hi11
Positions 0 to 11 in reading order. Position k is row ⌊k / 4⌋, column k mod 4.
Step 2 / 4

lo0mid5hi11row1col1
Position 5 is row 5 / 4 = 1, column 5 mod 4 = 1, holding 17. 17 < 20: lo = 6.
Step 3 / 4

lo6mid8hi11row2col0
Position 8 is row 8 / 4 = 2, column 8 mod 4 = 0, holding 29. 29 > 20: hi = 7.
Step 4 / 4

mid6row1col2
Position 6 is (1, 2), which holds 20: found.

TimeO(log(m × n))

SpaceO(1)

Sorted along rows and columns

A weaker promise: every row increases left to right and every column top to bottom, but rows overlap. The reading order is no longer sorted, and no single binary search works. Start at the top-right corner instead. Everything to its left in that row is smaller and everything below it in that column is larger, so one comparison discards a whole row or a whole column.

Staircase search

search(M, target)

Start at row 0, column n − 1.
If the value equals the target, return true.
If it is larger, the whole column below is larger too: move left.
If it is smaller, the whole row to the left is smaller too: move down.
If you leave the matrix, return false.

Looking for 19, starting at the top-right corner.

Step 1 / 7

row0col4
Start at the top-right corner, 20: the largest in its row, the smallest in its column.
Step 2 / 7

row0col3
20 > 19: everything below 20 in its column is larger still. Discard the column, move left.
Step 3 / 7

row1col3
14 < 19: everything left of 14 in its row is smaller still. Discard the row, move down.
Step 4 / 7

row2col3
17 < 19: everything left of 17 in its row is smaller still. Discard the row, move down.
Step 5 / 7

row2col2
21 > 19: everything below 21 in its column is larger still. Discard the column, move left.
Step 6 / 7

row3col2
16 < 19: everything left of 16 in its row is smaller still. Discard the row, move down.
Step 7 / 7

row3col2
19 = 19: found.

TimeO(m + n)

SpaceO(1)

Each step leaves one row or one column for good. A binary search in every row costs O(m log n), which is better only when there are few rows.

Why the second kind cannot be done in log time

Look at the cells on the diagonal running from bottom-left to top-right. The ordering of rows and columns says nothing about how they compare with each other, so any of them could hold the target, and checking one tells you nothing about the others. With min(m, n) such cells, any method needs that many reads in the worst case. The staircase walk is optimal for square matrices.

Be careful which matrix you have been given. "Rows sorted, and each row starts after the previous one ends" is the first kind; "rows sorted and columns sorted" is the second. Interviewers sometimes ask both in a row to see whether you notice.

Problems in this module

The k-th smallest value of a row-and-column-sorted matrix is in the last module, where it is solved by counting.