# LeetCode 240 Search a 2D Matrix II (Med, Java, O(m+n))

# Problem Description
- [LeetCode 240 Search a 2D Matrix II](https://leetcode.com/problems/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)

```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;
    }
}
```