LeetCode 74 · Binary Search

Search a 2D Matrix, explained with a picture

An elevator that searches a sorted apartment block.

MediumBinary Search
▶ Watch it step by step

The problem

You get a grid of numbers where each row is sorted left to right, and the first number of each row is bigger than the last number of the row before. Decide whether a target number is in the grid.

Input:  [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 16
Output: true

Picture it

Picture an apartment block: each floor is a row and apartment numbers keep increasing along a floor and then onto the next floor up. Read in order, the whole building is one long sorted list. So we binary search positions 0…(rows×cols − 1), and an elevator converts a position into (floor = position ÷ cols, door = position mod cols).

How to recognise it

  • The grid is sorted in reading order: each row is sorted, and each row starts after the previous row ends. Read row by row, it is one long sorted list.
  • You only need to know whether the target is there, and the problem asks for O(log(m · n)) time.
  • Any structure that can be numbered in sorted order can be binary searched, as long as you can turn a number back into a position. Here divmod does that.
  • Up to 100 × 100 cells.

Start with brute force

Check every row for the target.

def search_matrix_brute(m, target):
    return any(target in row for row in m)

Time is O(m · n) and space is O(1). With LeetCode's 100 × 100 limit that is at most 10^4 comparisons, which would pass, but the problem asks for O(log(m · n)): about 14 comparisons for the same grid. The brute force also ignores both kinds of order in the grid.

From brute force to the idea

  1. Find the waste. The grid is fully sorted, yet the brute force looks at every cell.
  2. Flatten it in your head. Number the cells 0 to rows * cols - 1 in reading order. Because each row starts above the end of the row before, these numbers list the values in sorted order.
  3. Turn a number back into a cell. Cell number mid is in row mid // cols and column mid % cols. divmod(mid, cols) gives both at once. Dividing by the number of columns is essential: each row holds cols cells.
  4. Run ordinary binary search. Keep lo..hi inclusive. Compare m[r][c] with the target and move lo or hi past mid, exactly as in a one-dimensional search.
  5. No list is built. The flattening is only arithmetic, so no copy of the grid is made.

This is the key idea: a grid sorted in reading order is one sorted list, and divmod(mid, cols) finds any position in it.

A two-step search also works: binary search the first column to find the row, then binary search that row. It has the same O(log m + log n) cost.

The key idea

Treat the 2-D grid as one sorted 1-D list and binary search it: O(log(rows × cols)).

Python solution

def search_matrix(m, target):
    rows, cols = len(m), len(m[0])
    lo, hi = 0, rows * cols - 1      # treat it as one long sorted list
    while lo <= hi:
        mid = (lo + hi) // 2
        r, c = divmod(mid, cols)       # which floor, which door
        if m[r][c] == target:
            return True
        if m[r][c] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return False

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(m · n): every cell may be checkedO(1)
Flattened binary search (shown code)O(log(m · n)): the range of cell numbers halves each stepO(1): a few integers

Edge cases

  • The example (target 16): returns True; target 13 returns False.
  • A 1 × 1 grid ([[5]]): lo == hi == 0, returns True for 5.
  • One row or one column ([[1, 3, 5]] or [[1], [3], [5]]): the arithmetic still works, since cols is 3 or 1.
  • Target outside the range (0 or 61 in the example): the range empties off one end and the function returns False.
  • Empty grid: len(m[0]) raises IndexError on []. LeetCode promises at least one row and column, so the shown code does not check.

Common mistakes

  • Using divmod(mid, rows). It only works by luck on square grids; on others it reads the wrong cell or goes out of range.
  • Setting hi = rows * cols and keeping while lo <= hi. When the target is larger than every value, mid reaches rows * cols and the code reads past the last row.
  • Using the staircase walk from the next exercise. It is correct here too, but O(m + n), not the O(log(m · n)) the problem asks for.
  • Binary searching only the rows by their first value and forgetting that the target may lie in the row before the first larger start.
Your turn: sorted rows and columns only

Now each row is sorted left to right and each column top to bottom, but a row may start below the end of the previous row (LeetCode 240). Flattening no longer gives a sorted list. Decide whether the target is present. Describe your approach, then write it if you like.

Compare with our answer

Start at the top-right corner. Everything below it in its column is bigger, and everything left of it in its row is smaller. So if the value is too big, the whole column is useless: move left. If it is too small, the whole row is useless: move down.

def staircase(m, target):
    r, c = 0, len(m[0]) - 1          # top-right corner
    while r < len(m) and c >= 0:
        if m[r][c] == target:
            return True
        if m[r][c] > target:
            c -= 1                   # whole column below is bigger too
        else:
            r += 1                   # whole row to the left is smaller too
    return False

Each step removes a row or a column, so time is O(m + n). Space is O(1).

A strong answer mentions: why the top-right (or bottom-left) corner works and the top-left does not, that each step discards a full row or column, and the O(m + n) bound.

Check what stuck

1. A grid stores 3,000 ticket numbers, 50 per row, sorted in reading order like this problem. Which approach finds whether a ticket number is present fastest?

2. Why must the shown code use divmod(mid, cols) and not divmod(mid, rows)?

3. A learner sets hi = rows * cols and keeps the rest of the shown code. With the example grid, which target now breaks it?

Score 60% or more and the lesson is marked complete.