Search a 2D Matrix

The problem

matrix is a table of integers, given as a list of rows that all have the same length. Every row is sorted from smallest to largest, and the first value of each row is larger than the last value of the row before it. Return true if target is somewhere in the table, and false if it is not.

What to write

function solve(matrix: number[][], target: number): boolean

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

Output
true

Input
matrix = [[1,3],[5,7]]
target = 4

Output
false

Constraints

The matrix has at least one cell.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   Looking at every cell works, but that ignores the two ordering rules. Together they are strong: a value is never smaller than a value to its left in the same row, or than any value in a row above it.

2. Hint 2: Ask a smaller question

   Copy the values of example 1 onto one line, row after row: 1, 3, 5, 7, 10, 11 and so on. What do you notice about the order of the values on that line? Would the same be true for any matrix that follows the two rules?

3. Hint 3: Name the pattern

   Read row by row, the values of the matrix form one sorted list, and a sorted list can be searched by halving: binary search on a sorted range. You never build that list. You only need to turn a position in the list into a row and a column. Read the lesson on binary search on a sorted range.

4. Hint 4: State the invariant

   Number the cells row by row, starting at 0. Keep a range of those numbers that holds the target's cell, if the target is there at all. With c columns, cell number p is in row p ÷ c, rounded down, and its column is the remainder of that division.

5. Hint 5: Sketch the pseudocode

   low = 0, high = rows × columns - 1. While low <= high: mid = the middle, rounded down. Read the cell in row mid ÷ columns, rounded down, at the column given by the remainder. Equal to the target: return true. Smaller: low = mid + 1. Larger: high = mid - 1. After the loop, return false.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Treat the matrix as a flattened sorted array and translate each midpoint into row and column coordinates.

The slow way

Look at every cell, row by row, and return true as soon as one cell equals the target. This is correct, but a matrix with 1,000 rows and 1,000 columns has a million cells to look at, and the two ordering rules go unused.

The insight

The first value of each row is larger than the last value of the row before it, so the rows joined end to end are one sorted list. You do not have to build that list. With 4 columns, position 5 of the list is the cell in row 1, column 1, because 5 ÷ 4 is 1 with remainder 1. Positions, rows and columns are all counted from 0.

Step by step

1. Treat the rows, joined end to end, as one sorted list. Each row starts above the last value of the row before it, so reading row after row never goes down. Number the cells from 0 to rows × columns - 1, and search while that range still holds a position.
2. Look at the middle position of the range. As in a plain sorted list, the middle leaves at most half of the positions to search, whichever way the comparison goes.
3. Turn that position into a row and a column and read the value. Every row holds the same number of values. So the position divided by that number, rounded down, is the row, and the remainder is the column.
4. The value is the target: it is in the matrix. The question is only whether the target is present, so one matching cell is enough to answer true.
5. The value is too small: the target can only come later. Every earlier position holds a smaller value still, so this position and all the positions before it leave the range.
6. The value is too large: the target can only come earlier. Every later position holds a larger value still, so this position and all the positions after it leave the range.
7. No position is left: the target is not in the matrix. Every cell has been ruled out by a comparison, so no cell is left that could hold the target.

The same numbered steps are the comments in each solution.

function solve(matrix, target) {
  // 1. Treat the rows, joined end to end, as one sorted list
  const cols = matrix[0].length;
  let l = 0,
    r = matrix.length * cols - 1;
  while (l <= r) {
    // 2. Look at the middle position of the range
    const m = Math.floor((l + r) / 2);
    // 3. Turn that position into a row and a column and read the value
    const v = matrix[Math.floor(m / cols)][m % cols];
    // 4. The value is the target: it is in the matrix
    if (v === target) return true;
    // 5. The value is too small: the target can only come later
    if (v < target) l = m + 1;
    // 6. The value is too large: the target can only come earlier
    else r = m - 1;
  }
  // 7. No position is left: the target is not in the matrix
  return false;
}

function solve(matrix: number[][], target: number): boolean {
  // 1. Treat the rows, joined end to end, as one sorted list
  const cols = matrix[0].length;
  let l = 0,
    r = matrix.length * cols - 1;
  while (l <= r) {
    // 2. Look at the middle position of the range
    const m = Math.floor((l + r) / 2);
    // 3. Turn that position into a row and a column and read the value
    const v = matrix[Math.floor(m / cols)][m % cols];
    // 4. The value is the target: it is in the matrix
    if (v === target) return true;
    // 5. The value is too small: the target can only come later
    if (v < target) l = m + 1;
    // 6. The value is too large: the target can only come earlier
    else r = m - 1;
  }
  // 7. No position is left: the target is not in the matrix
  return false;
}

def solve(matrix, target):
    # 1. Treat the rows, joined end to end, as one sorted list
    cols = len(matrix[0])
    left, right = 0, len(matrix) * cols - 1
    while left <= right:
        # 2. Look at the middle position of the range
        mid = (left + right) // 2
        # 3. Turn that position into a row and a column and read the value
        row, col = divmod(mid, cols)
        value = matrix[row][col]
        # 4. The value is the target: it is in the matrix
        if value == target:
            return True
        # 5. The value is too small: the target can only come later
        if value < target:
            left = mid + 1
        # 6. The value is too large: the target can only come earlier
        else:
            right = mid - 1
    # 7. No position is left: the target is not in the matrix
    return False

Example 1, traced

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

Output
true

Why it works

Read row by row, the values are in sorted order, so the positions behave like one sorted list. A value that is too small rules out its own position and every earlier one. A value that is too large rules out its own position and every later one. Dividing by the row length gives each position exactly one cell.

Time and space

Time O(log(rows · cols)), extra space O(1). There are rows × cols positions, and each round leaves at most half of them. The number of rounds is how many times that count can be halved, its logarithm: O(log(rows · cols)), at most 20 rounds for a million cells. Only a few numbers are stored: O(1) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Divide by the number of columns, not the number of rows. Example 1 has 3 rows and 4 columns, so position 11 is row 2, column 3. Dividing by 3 asks for row 3, which does not exist.
• Keep searching while the range holds at least one position. In example 1 the last range is position 1 alone, where the 3 sits. Stopping when the two ends meet never looks there and returns false.
• Do not copy the rows into one long list first. The answer comes out right, but the copy touches every cell, which is the work the search is meant to avoid.

Pattern

Binary search on a sorted range. Builds on Binary Search.

Keep going