Search a 2D Matrix

MediumBinary searchLeetCode 74 ↗World 2-19

0:00 / 0:00

Each row is sorted and starts above the last row's end, so the grid is one sorted list in disguise: binary search it with row and column math.

▼

The problem

LeetCode 74 (Medium). An m × n integer matrix has every row sorted, and the first value of each row is greater than the last value of the row before it. Given target, return true if it is in the matrix, else false.

Examples (LeetCode's): matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 → true (walked through in scene 6) and the same matrix, target = 13 → false (scene 7).

TRY IT ON LEETCODE ▶

The solution

def searchMatrix(matrix, target):
    m, n = len(matrix), len(matrix[0])
    lo, hi = 0, m * n - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        v = matrix[mid // n][mid % n]
        if v == target:
            return True
        if v < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return False

Transcript

Search a 2D Matrix. Every row is sorted, and every row starts higher than the row before it ends. Is a target in the matrix? Return true or false.

Three rows of four: one, three, five, seven; ten, eleven, sixteen, twenty; twenty-three, thirty, thirty-four, sixty. Target three is in the first row: true. Target thirteen belongs between eleven and sixteen, but it's missing: false.

The naive way checks every cell: m times n. Binary search on each row is quicker, m times log n, but still visits every row.

The key: read the rows in order, and you get one sorted list of twelve numbers. So binary search the positions, zero to eleven. Position p lives in row p divided by n, column p mod n. Position seven: row one, column three, twenty.

In code, low starts at zero, and high at m times n, minus one. Take the middle, map it to its cell, and compare. Equal: return true. Too small: move low right. Too big: move high left.

Target three. Middle five: row one, column one, eleven. Too big, so high drops to four. Middle two: five, still too big. Middle zero: one, too small. Middle one: three. Found it.

Target thirteen. Middle five: eleven, too small, so low jumps to six. Middle eight: twenty-three, too big. Middle six: sixteen, too big. Low passes high: false.

Each step halves the range: order log of m times n time, and order one space.

One sorted list, one binary search, mapped back to the grid. That's Search a 2D Matrix.