MediumArrayBinary SearchMatrix

Search a 2D Matrix II

1 approach, code in every language

You are given a matrix in which every row is sorted in ascending order from left to right and every column is sorted in ascending order from top to bottom. Given a target value, decide whether it exists somewhere in the matrix.

Unlike a fully sorted grid, the rows and columns are only individually sorted, so a plain binary search over a flattened view will not work. You need a strategy that exploits both orderings at once.

Example 1

Input: matrix = [[1, 4, 7], [2, 5, 8], [3, 6, 9]], target = 5

Output: true

Following the ordering from the top-right corner leads to the cell holding 5, so the target is present.

Example 2

Input: matrix = [[1, 4, 7], [2, 5, 8], [3, 6, 9]], target = 10

Output: false

The largest value in the matrix is 9, so 10 cannot be found anywhere.

Constraints

1 <= m, n <= 300
-10^9 <= matrix[i][j] <= 10^9
Each row is sorted in ascending order
Each column is sorted in ascending order

Staircase Search from a Corner

Begin at the top-right corner and eliminate a full row or a full column at each step based on the comparison with the target.

Loading animation…

Intuition

The top-right cell is special: it is the largest value in its row and the smallest value in its column. That gives a clean decision rule. If the current value is bigger than the target, the entire current column is too big, so drop it by moving left. If the current value is smaller than the target, the entire current row is too small, so drop it by moving down. Each comparison discards one row or one column, so the search converges quickly toward a match or off the edge of the grid.

Algorithm walkthrough

1Start at row = 0 and col = n - 1, the top-right corner.
2Read value = matrix[row][col].
3If value equals target, return true immediately.
4If value is greater than target, decrement col to discard the current column; otherwise increment row to discard the current row.
5Repeat until you fall off the grid, at which point return false.

Implementation

from typing import List


class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix or not matrix[0]:
            return False
        row, col = 0, len(matrix[0]) - 1
        while row < len(matrix) and col >= 0:
            value = matrix[row][col]
            if value == target:
                return True
            elif value > target:
                col -= 1
            else:
                row += 1
        return False

Time

O(m + n)

Space

O(1)

Every iteration removes a row or a column, bounding the number of steps by m + n.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Search

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free