Problem Description

• LeetCode 240 Search a 2D Matrix II

LeetCode 240 (Search a 2D Matrix II) asks us to search for a target value in an m×n matrix with special properties:

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

The challenge is to determine if the target exists in the matrix efficiently, leveraging these sorted properties.

Key constraints:

• Matrix dimensions: m, n ≤ 300
• Matrix values and target: -10⁹ ≤ value ≤ 10⁹
• Matrix can be null or empty

Example matrix:

[1,  4,  7,  11]
[2,  5,  8,  12]
[3,  6,  9,  16]
[10, 13, 14, 17]

Core Algorithm Walkthrough

The solution uses a staircase search algorithm that starts from the top-right corner and eliminates entire rows or columns based on comparisons.

Key Insight

Starting from the top-right corner gives us optimal elimination power:

• Current value > target: Entire column to the right can be eliminated (move left)
• Current value < target: Entire row above can be eliminated (move down)
• Current value = target: Found the target

Algorithm Steps

1. Initialize pointers: Start at top-right corner (row = 0, col = matrix[0].length - 1)

2. Iterative elimination:

   • Compare current element with target
   • If equal: return true
   • If current > target: move left (col--) - eliminates current column
   • If current < target: move down (row++) - eliminates current row

3. Termination: Continue until pointers go out of bounds

Example Trace: Searching for target = 5

Matrix:
[1,  4,  7,  11]
[2,  5,  8,  12]  
[3,  6,  9,  16]
[10, 13, 14, 17]

Start: row=0, col=3, corner=11
11 > 5 → move left: col=2

row=0, col=2, corner=7  
7 > 5 → move left: col=1

row=0, col=1, corner=4
4 < 5 → move down: row=1

row=1, col=1, corner=5
5 == 5 → return true

The algorithm eliminated columns 3 and 2, then row 0, efficiently narrowing the search space.

Complexity Analysis

• Time Complexity: O(m + n) where m is rows and n is columns. In the worst case, we traverse from top-right to bottom-left, visiting at most m + n elements.
• Space Complexity: O(1) - only using constant extra space for row/column pointers.

This is significantly better than naive O(mn) brute force search and more efficient than applying binary search to each row O(m log n).

Full Solution (Java)

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length < 1 || matrix[0].length < 1) {
            return false;
        }

        // Start from top-right corner
        int col = matrix[0].length - 1;
        int row = 0;

        while (col >= 0 && row <= matrix.length - 1) {
            int corner = matrix[row][col];
            if (target == corner) {
                return true;
            } else if (target < corner) {
                col--;  // Eliminate current column
            } else if (target > corner) {
                row++;  // Eliminate current row
            }
        }

        return false;
    }
}