#74

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Search a 2D Matrix

Search a 2D matrix efficiently using binary search over its linearized index, ensuring correctness in row-major sorted arrays.

array binary search matrix

Problem Statement

You are given an m x n integer matrix where each row is sorted in ascending order and the first integer of each row is greater than the last integer of the previous row. Given an integer target, you must determine whether the target exists in the matrix. The solution must leverage the matrix's sorted structure to minimize unnecessary comparisons and avoid linear scans.

Return true if the target exists in the matrix or false otherwise. You are required to implement an approach that treats the 2D matrix as a flattened sorted array, performing binary search over indices while correctly translating them to row and column coordinates. The algorithm must maintain O(log(m * n)) time complexity and handle edge cases such as the smallest or largest elements.

Examples

Example 1

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

Output: true

Example details omitted.

Example 2

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

Output: false

Example details omitted.

Constraints

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104

Solution Approach

Flatten Matrix and Apply Binary Search

Conceptually treat the 2D matrix as a 1D array of length m * n, where each index maps to a row and column via row = index / n and col = index % n. Initialize left and right pointers at 0 and m * n - 1, and iteratively check the middle index. If the value equals the target, return true; otherwise, adjust left or right depending on the comparison. This approach ensures all comparisons use the sorted property and never revisits elements unnecessarily.

Edge Handling and Boundary Mapping

Pay careful attention when computing the middle index and translating it back to matrix coordinates to avoid off-by-one errors. Since each row is individually sorted and the first element of each row is larger than the previous row's last, the mapping ensures correct access to values. Handle cases where the target is smaller than the first element or larger than the last element to exit early, preventing redundant search iterations and maintaining consistent O(log(m * n)) performance.

Avoid Linear Search in Rows

Do not scan rows linearly even if the target might be close to a row boundary; doing so violates the required logarithmic complexity. Instead, rely entirely on the virtual 1D index binary search to navigate the matrix. This ensures that every decision halves the search space. Additionally, avoid common mistakes such as using mid incorrectly or assuming the matrix is rectangular without validating the number of columns. Correctly managing the virtual flattening preserves efficiency and prevents subtle off-by-one failures.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The binary search over the flattened matrix ensures a time complexity of O(log(m * n)) because each iteration halves the search space. Space complexity remains O(1) as only pointers and a few integer variables are used for mapping indices to rows and columns, with no additional arrays or recursion overhead.

What Interviewers Usually Probe

Do you understand how to map a 1D index back to 2D coordinates in the matrix?
Can you adjust your binary search if the target is smaller than the first element or larger than the last?
Will you maintain O(log(m * n)) complexity without scanning any row linearly?

Common Pitfalls or Variants

Common pitfalls

Miscomputing row and column from a 1D index leading to wrong value comparisons.
Attempting linear search in individual rows which breaks the logarithmic time requirement.
Incorrect handling of edge targets that match the first or last element of the matrix, causing off-by-one errors.

Follow-up variants

Search a 2D matrix II where rows and columns are independently sorted but not fully flattened.
Search a rotated 2D matrix with unknown rotation point while preserving sorted property in rows.
Find the k-th smallest element in a sorted 2D matrix using a similar binary search over value space.

FAQ

How does binary search apply to Search a 2D Matrix?

Binary search treats the 2D matrix as a virtual flattened array, allowing logarithmic search by mapping indices to rows and columns instead of scanning linearly.

What happens if the target is the first or last element?

The algorithm correctly identifies targets at matrix boundaries by computing the mid-point mapping and avoids off-by-one errors during index translation.

Can this approach handle non-rectangular matrices?

The standard solution assumes all rows have equal columns; non-rectangular matrices require additional checks or adjusted index mapping to preserve correctness.

Why is linear row search incorrect here?

Linear row scanning violates the O(log(m * n)) requirement and misses the optimization gained from binary search over the fully flattened matrix index space.

What is the key failure mode in this problem?

A common failure mode is miscalculating row and column from the 1D index, which causes false negatives or incorrect comparisons during binary search iterations.

terminal

Solution

Solution 1: Binary Search

We can logically unfold the two-dimensional matrix and then perform binary search.

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        left, right = 0, m * n - 1
        while left < right:
            mid = (left + right) >> 1
            x, y = divmod(mid, n)
            if matrix[x][y] >= target:
                right = mid
            else:
                left = mid + 1
        return matrix[left // n][left % n] == target

Solution 2: Search from the Bottom Left or Top Right

Here, we start searching from the bottom left corner and move towards the top right direction. We compare the current element $matrix[i][j]$ with $target$:

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        left, right = 0, m * n - 1
        while left < right:
            mid = (left + right) >> 1
            x, y = divmod(mid, n)
            if matrix[x][y] >= target:
                right = mid
            else:
                left = mid + 1
        return matrix[left // n][left % n] == target

Continue Practicing

#240 search a 2d matrix ii #363 max sum of rectangle no larger than k #378 kth smallest element in a sorted matrix