[Medium] 240. Search a 2D Matrix II

Write an efficient algorithm that searches for a value target in an m x n integer matrix. This matrix has the following properties:

  • Integers in each row are sorted in ascending from left to right.
  • Integers in each column are sorted in ascending from top to bottom.

Examples

Example 1:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true

Matrix visualization:

[ 1,  4,  7, 11, 15]
[ 2,  5,  8, 12, 19]  ← target = 5 found here
[ 3,  6,  9, 16, 22]
[10, 13, 14, 17, 24]
[18, 21, 23, 26, 30]

Example 2:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
Output: false

Matrix visualization:

[ 1,  4,  7, 11, 15]
[ 2,  5,  8, 12, 19]
[ 3,  6,  9, 16, 22]
[10, 13, 14, 17, 24]
[18, 21, 23, 26, 30]

Target = 20 not found in matrix

Constraints

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 300
  • -10^9 <= matrix[i][j] <= 10^9
  • All the integers in each row are sorted in ascending order.
  • All the integers in each column are sorted in ascending order.
  • -10^9 <= target <= 10^9

Solution 1: Binary Search per Row

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

Search each row using binary search.

class Solution:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        if not matrix or not matrix[0]:
            return False
        rows, cols = len(matrix), len(matrix[0])
        
        for i in range(rows):
            left, right = 0, cols - 1
            while left <= right:
                mid = left + (right - left) // 2
                if matrix[i][mid] == target:
                    return True
                elif matrix[i][mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1
        return False

How it Works:

  1. Iterate through each row
  2. Binary search within each row for the target
  3. Return true if found in any row, false otherwise

Solution 2: Divide and Conquer

Time Complexity: O(n log n) average case
Space Complexity: O(log n) for recursion stack

Use divide and conquer by eliminating regions based on the middle column.

class Solution:
    def searchMatrixHelper(self, matrix: list[list[int]], target: int, 
                          top: int, left: int, bottom: int, right: int) -> bool:
        if top > bottom or left > right:
            return False
        if target < matrix[top][left] or target > matrix[bottom][right]:
            return False
        
        midCol = left + (right - left) // 2
        row = top
        
        # Find the last row where matrix[row][midCol] <= target
        while row <= bottom and matrix[row][midCol] <= target:
            if matrix[row][midCol] == target:
                return True
            row += 1
        
        # Search in top-right and bottom-left quadrants
        return (self.searchMatrixHelper(matrix, target, top, midCol + 1, row - 1, right) or
                self.searchMatrixHelper(matrix, target, row, left, bottom, midCol - 1))
    
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        if not matrix or not matrix[0]:
            return False
        return self.searchMatrixHelper(matrix, target, 0, 0, len(matrix) - 1, len(matrix[0]) - 1)

How it Works:

  1. Choose middle column and find the boundary where elements ≤ target
  2. Eliminate regions: Search only in top-right and bottom-left quadrants
  3. Recursively search the remaining regions

Time Complexity: O(m + n)
Space Complexity: O(1)

Start from top-right corner and eliminate row or column at each step.

class Solution:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        if not matrix or not matrix[0]:
            return False
        rows, cols = len(matrix), len(matrix[0])
        row, col = 0, cols - 1
        
        while row < rows and col >= 0:
            if matrix[row][col] == target:
                return True
            elif matrix[row][col] > target:
                col -= 1  # Eliminate current column
            else:
                row += 1  # Eliminate current row
        return False

How it Works:

  1. Start from top-right corner (matrix[0][cols-1])
  2. Compare with target:
    • If equal: found target
    • If greater: eliminate current column (move left)
    • If smaller: eliminate current row (move down)
  3. Continue until target found or out of bounds

Algorithm Comparison

Solution Time Complexity Space Complexity Approach
Binary Search per Row O(m log n) O(1) Search each row
Divide and Conquer O(n log n) avg O(log n) Recursive elimination
Top-Right Search O(m + n) O(1) Optimal elimination

Visual Example

For target = 5 in the matrix:

[ 1,  4,  7, 11, 15]
[ 2,  5,  8, 12, 19]  ← Found here!
[ 3,  6,  9, 16, 22]
[10, 13, 14, 17, 24]
[18, 21, 23, 26, 30]

Top-Right Search Path:

  1. Start at 15 (top-right)
  2. 15 > 5 → move left to 11
  3. 11 > 5 → move left to 7
  4. 7 > 5 → move left to 4
  5. 4 < 5 → move down to 5
  6. 5 == 5 → Found!

Search Path Visualization:

[ 1,  4,  7, 11, 15] ← Start here
[ 2,  5,  8, 12, 19] ← End here (found!)
[ 3,  6,  9, 16, 22]
[10, 13, 14, 17, 24]
[18, 21, 23, 26, 30]

Path: 15 → 11 → 7 → 4 → 5 ✓

Key Insights

  1. Matrix properties allow elimination strategies
  2. Top-right approach is optimal with O(m + n) time
  3. Binary search per row is simple but not optimal
  4. Divide and conquer provides good average performance
  5. Elimination strategy leverages sorted properties

Why Top-Right Works

  • If current element > target: All elements in current column are ≥ current element, so eliminate column
  • If current element < target: All elements in current row are ≤ current element, so eliminate row
  • Each step eliminates either a row or column, guaranteeing O(m + n) steps