#29 Medium Time O(log(m·n)) Space O(1) Animated

Search a 2D Matrix

Efficiently search in an m x n matrix where rows and columns are sorted.

LeetCode ↗

Tutor Mode Build the mental model before you memorize the code.

1 Predict
2 Trace
3 Explain
4 Implement

Pattern Binary search over a monotonic decision

Each comparison proves that half of the remaining search space cannot contain the answer.

Approach: Binary Search — Flattened Matrix

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Core Insight

Each comparison proves that half of the remaining search space cannot contain the answer.

Common Pitfall

Choose inclusive or exclusive bounds once and update them consistently.

Description

Efficiently search in an m x n matrix where rows and columns are sorted.

Constraints

Time Complexity: O(log(m·n))
Space Complexity: O(1)

Solution — Binary Search — Flattened Matrix

TimeO(log(m·n)) SpaceO(1)

Implementation Plan

Translate the invariant into these small, testable moves.

Set the initial bounds.
Compute a midpoint.
Use the monotonic condition to discard one half.
Return when found or when the bounds cross.

def searchMatrix(matrix, target):
    rows, cols = len(matrix), len(matrix[0])
    left, right = 0, rows * cols - 1
    while left <= right:
        mid = (left + right) // 2
        value = matrix[mid // cols][mid % cols]
        if value == target:
            return True
        if value < target:
            left = mid + 1
        else:
            right = mid - 1
    return False

Binary Search

Koko Eating Bananas

Search a 2D Matrix

Steps

Description

Constraints

Tags

Solution — Binary Search — Flattened Matrix