Search a 2D Matrix

Q: What is the time complexity of Search a 2D Matrix?

Binary search over the flattened grid runs in O(log(m × n)) time and O(1) space: at most 14 comparisons for 10000 cells. Since log(m × n) = log m + log n , it matches searching for the row and then inside it.

Q: Should you use the top-right corner walk or binary search?

The corner walk takes O(m + n) steps and only needs rows and columns sorted, so it also solves the variant where a row may start below the end of the row above. When each row starts above the previous one ends, as here, binary search is faster.

Q: Is two binary searches, one for the row and one inside it, also correct?

Yes. Binary search the first column for the last row whose first value is at most target , then binary search that row. It runs in O(log m + log n) , the same bound. The single search does the same work with one loop and fewer edge cases.

MediumBinary search

+10

You get a grid of integers matrix with m rows and n columns, and an integer target. Every row is sorted in increasing order, and the first value of each row is greater than the last value of the row above it. Return true if target appears in the grid and false otherwise, in O(log(m × n)) time.

Function

searchMatrix(matrix: integer-2d-array, target: integer) → boolean

matrixinteger-2d-array: the grid, given as a list of rows, sorted row by row
targetinteger: the value to look for
Returnsboolean: true if target is in the grid, false otherwise

Constraints

1 ≤ m, n ≤ 100, where m = matrix.length and n = matrix[i].length
Every row has the same length n.
-10⁴ ≤ matrix[i][j], target ≤ 10⁴
Each row is sorted in strictly increasing order, and the first value of each row is greater than the last value of the previous row.

Examples

Input: matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]]target = 26
Output: true
Explanation: Read row by row, the 12 values are one sorted list. A binary search over positions 0 to 11 checks 21 at position 5 (too small), 33 at position 8 (too big), then finds 26 at position 6.

Follow-up

Suppose the rows could have different lengths, still sorted end to end. How would you turn a position into a row and a column, and what would the search cost?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

The two ordering rules together make the grid, read row by row, one sorted list of m × n values. Binary search that list by position, and turn each position back into a row and a column with one division. A 100 by 100 grid then needs at most 14 comparisons instead of 10000.

Check every cell

Intuition

Compare every cell with target and return true on a match, false after the last cell. It reads every cell, so it is correct for any grid, sorted or not. It never uses the order, so a 100 by 100 grid costs up to 10000 comparisons.

Algorithm

For each row of matrix, look at each value in order.
If the value equals target, return true.
After the loops, return false.

def searchMatrix(matrix, target):
    for row in matrix:
        for value in row:
            if value == target:
                return True
    return False

Walk from the top-right corner

Intuition

From the top-right cell, every value to the left is smaller and every value below is larger. If the cell is larger than target, the column below it is larger too: step left and drop that column. If it is smaller, the row to its left is smaller too: step down and drop that row.

In the first example, 14 is smaller than 26, so step down to 30. 30 is larger, so step left to 26, a match. Each step removes a row or a column, so you take at most m + n steps: 200 for a 100 by 100 grid. The walk only needs rows and columns sorted, so it ignores half of what this grid gives you.

Algorithm

Start at row 0 and the last column.
While the row and the column are inside the grid, read the cell.
If it equals target, return true.
If it is larger, move one column left; if it is smaller, move one row down.
When you leave the grid, return false.

def searchMatrix(matrix, target):
    # Start at the top-right corner: left is smaller, down is larger.
    r, c = 0, len(matrix[0]) - 1
    while r < len(matrix) and c >= 0:
        value = matrix[r][c]
        if value == target:
            return True
        if value > target:
            c -= 1  # every value below in this column is larger still
        else:
            r += 1  # every value to the left in this row is smaller still
    return False

Binary search over the flattened grid

Intuition

Number the cells row by row: row 0 holds positions 0 to n - 1, row 1 holds n to 2n - 1, and so on. Each row is sorted and starts above where the previous row ended, so values only go up with position. That is a sorted list, and binary search applies.

You never build the list. Position p is in row p / n and column p % n, with integer division. In the first example n = 4, so position 6 is row 1, column 2, which holds 26. Each comparison halves the positions that could hold target: at most 14 for 10000 cells, with two indexes of extra memory.

Algorithm

Let m and n be the number of rows and columns, and set lo = 0, hi = m × n - 1.
While lo ≤ hi, take mid halfway between them.
Read value = matrix[mid / n][mid % n].
If value equals target, return true. If it is smaller, set lo = mid + 1; otherwise set hi = mid - 1.
When the loop ends, return false.

def searchMatrix(matrix, target):
    rows, cols = len(matrix), len(matrix[0])
    # Read row by row, the cells form one sorted list of rows * cols values.
    # Position p of that list is matrix[p // cols][p % cols].
    lo, hi = 0, rows * cols - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        value = matrix[mid // cols][mid % cols]
        if value == target:
            return True
        if value < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return False

Pitfalls and edge cases

Dividing by the number of rows instead of columns. Position p is in row p / n; with m in its place the code passes on square grids and fails on 3 rows and 4 columns.
In the two-search version, not handling target below matrix[0][0]. No row starts at or below it, and a row index of -1 reaches the second search.
Looping on lo < hi with an inclusive hi. A 1 by 1 grid holding target returns false, because the loop never runs.
In Lua and R, forgetting the shift to 1-based indexes: position p is row p / n + 1, column p % n + 1.

Frequently asked questions3

What is the time complexity of Search a 2D Matrix?

Binary search over the flattened grid runs in O(log(m × n)) time and O(1) space: at most 14 comparisons for 10000 cells. Since log(m × n) = log m + log n, it matches searching for the row and then inside it.

Should you use the top-right corner walk or binary search?

The corner walk takes O(m + n) steps and only needs rows and columns sorted, so it also solves the variant where a row may start below the end of the row above. When each row starts above the previous one ends, as here, binary search is faster.

Is two binary searches, one for the row and one inside it, also correct?

Yes. Binary search the first column for the last row whose first value is at most target, then binary search that row. It runs in O(log m + log n), the same bound. The single search does the same work with one loop and fewer edge cases.

def searchMatrix(matrix, target):
    # Write code here

Test #1

Test #2

Arguments

matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]]
target = 26

Expected Output

true

Search a 2D Matrix

Function

Constraints

Examples

Hints

Solution

Check every cell

Walk from the top-right corner

Binary search over the flattened grid

Pitfalls and edge cases

Frequently asked questions3

Similar problems