4.8 Search a 2D Matrix II

4.8.1 Problem Metadata

• Platform: LeetCode
• Problem ID: 240
• Difficulty: Medium
• URL: https://leetcode.com/problems/search-a-2d-matrix-ii/
• Tags:
• Techniques: Matrix Traversal, Matrix

4.8.2 Description

The matrix is sorted in ascending order both across rows and down columns. Determine whether a target value exists.

4.8.3 Examples

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

4.8.4 Constraints

• 1 <= m, n <= 300

4.8.5 Solution - Staircase Search

4.8.5.1 Walkthrough

Start in the top-right corner (or bottom-left). At each step:

• If the value is greater than target, move left (eliminate a column).
• If smaller, move down (eliminate a row).

Because of the sorted property, one direction always reduces the search space.

4.8.5.2 Analysis

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

4.8.5.3 Implementation Steps

1. Set row = 0, col = n - 1.
2. While row < m and col >= 0:
   • If matrix[row][col] == target, return true.
   • If greater, col--; otherwise row++.
3. Return false if not found.

4.8.5.4 Code - Java

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

    int row = 0;
    int col = matrix[0].length - 1;

    while (row < matrix.length && col >= 0) {
        int value = matrix[row][col];
        if (value == target) {
            return true;
        } else if (value > target) {
            col--;
        } else {
            row++;
        }
    }

    return false;
}