Domain 2MediumCORE

Search a 2D Matrix

We are given a 2D matrix where each row is sorted in ascending order from left to right. Crucially, there is no overlap between rows: the first element of any specific row is strictly greater than the last element of the previous row (e.g., matrix[i][0] > matrix[i-1][-1]).

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Array#Binary Search

74. Search a 2D Matrix

Model: qwen3.5:9b
Topics: Array,Binary Search
FAANG asked: 1
Acceptance rate: 38.1%


Problem Breakdown

We are given a 2D matrix where each row is sorted in ascending order from left to right. Crucially, there is no overlap between rows: the first element of any specific row is strictly greater than the last element of the previous row (e.g., matrix[i][0] > matrix[i-1][-1]).

Inputs:

  • matrix: A list of lists containing integers (m rows, n columns).
  • target: An integer value to search for.

Outputs:

  • Boolean: Returns True if the target exists in the matrix, otherwise False.

Constraints & Edge Cases:

  • Dimensions 1≤m,n≤1001 \le m, n \le 100. This is small enough that even linear scan passes easily (O(mn)O(mn)), but we are asked for an efficient algorithm.
  • Values range from -10^4 to 10^4 (no overflow issues in standard integer types).
  • The constraints guarantee non-empty rows/columns, so m and n will be at least 1. However, robust code should handle the logic gracefully if dimensions were larger or empty.

Intuition

If we iterate through every element to find the target, that is a brute-force approach with O(m×n)O(m \times n) time complexity. Given the sorted nature of both rows and columns (specifically across row boundaries), this structure implies something powerful: the entire matrix can be treated as a single 1D sorted array.

Imagine flattening [[1,3],[4,5]] into [1,3,4,5]. The property that the first element of each row is greater than the last of the previous ensures there are no “dips” between rows. This means we can apply Binary Search directly on this virtual 1D array rather than iterating linearly or doing nested loops.

The key insight is mapping a hypothetical index mid in this flattened space back to actual matrix coordinates (row, col). If the value at that coordinate matches our target, return true; if it’s smaller, we search right (higher indices); if larger, search left. This reduces complexity from linear O(mn)O(mn) or even row-by-row binary search (O(log⁡m+log⁡n)O(\log m + \log n) with overhead) to a single logarithmic pass over the total number of elements.

Approach

  1. Define Search Space: The virtual array has length m * n. We set our left pointer (left) at index 0 and right pointer (right) at m * n - 1.
  2. Binary Search Loop: While left <= right:
    • Calculate the middle index: mid = (left + right) // 2.
  3. Coordinate Mapping: Convert this flat mid index back to matrix coordinates using integer division and modulo arithmetic:
    • Row index: row = mid // n
    • Column index: col = mid % n
  4. Comparison: Access the value at matrix[row][col].
    • If equal, return True.
    • If smaller than target (val < target), move left pointer to mid + 1.
    • If larger (val > target), move right pointer to mid - 1.
  5. Termination: If the loop completes without finding the value, return False.

Complexity Analysis

  • Time Complexity: O(log⁡(m×n))O(\log(m \times n)). Since we are performing binary search over a total of m⋅nm \cdot n elements, and log⁡(mn)=log⁡m+log⁡n\log(mn) = \log m + \log n, this is optimal for sorted data. In the worst case (e.g., 100x100), operations count is roughly log⁡(10000)≈14\log(10000) \approx 14.
  • Space Complexity: O(1)O(1). We only use a constant amount of extra space for pointers and indices, regardless of input size.

Solution

def searchMatrix(matrix: list[list[int]], target: int) -> bool:
    if not matrix or not matrix[0]:
        return False
    
    m = len(matrix)      # Number of rows
    n = len(matrix[0])   # Number of columns (width)
    
    left, right = 0, m * n - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        # Map the flat index 'mid' back to row and column indices
        row_idx = mid // n
        col_idx = mid % n
        
        current_val = matrix[row_idx][col_idx]
        
        if current_val == target:
            return True
        elif current_val < target:
            left = mid + 1
        else:
            right = mid - 1
            
    return False

Edge Cases Handled

  • Single Element Matrix: The loop handles left and right converging on the single index correctly.
  • Target Outside Range: If target is smaller than min or larger than max, binary search naturally narrows pointers until they cross (left > right) without infinite loops.
  • Negative Values: Comparison logic works identically for negative integers as positive ones in Python/standard integer arithmetic.
  • Constraints Compliance: The code assumes valid input per constraints (m,n≥1m,n \ge 1), but includes a quick check at the start to prevent index errors if an empty matrix were passed unexpectedly (defensive programming).