0240.Search a 2D Matrix II

Link: 240. Search a 2D Matrix II - Medium
Track: Amazon Tag

Question

Restate

Given an m x n integer matrix matrix where:

• Each row is sorted in ascending order (left → right)
• Each column is sorted in ascending order (top → bottom)
  Return True if target exists in the matrix, otherwise return False.

Edge Case

• Empty matrix
• Single element

---

Method 1 - Staircase Search, O($m\ast n$)
Method 2 - Binary Search Each Row, O$(mlogn$)

Method

Approach

• Start at (row=0, col=n-1) (top-right).
• While inside bounds:
  • If equal → return True
  • If too big → col -= 1
  • If too small → row += 1
• If out of bounds → return False

Complexity

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

Code

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

---

History

• Feb-16-2026 Solved
  • Struggle with boundaries
  • time complexity
• Feb-15-2026 Peeked
  • wrong approach