Algorithm-Day21-Search-a-2D-Matrix-II-lc-240

Posted on In , Views:

🧩 Problem Description

Write an efficient algorithm that searches for a value in an m x n matrix.

This matrix has the following properties:

  • Integers in each row are sorted in ascending order.
  • Integers in each column are sorted in ascending order.

Example:

1
2
3
4
5
6
7
8
9
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

💡 Naive Approach (Not Ideal)

  • Scan the whole matrix: O(m × n) time.
  • ❌ Not efficient considering the sorted properties.

💡 Optimal Approach: Search from Top-Right Corner

✨ Key Idea

  • Start from the top-right cell.
  • At each step:
    • If the value is equal to target, return true.
    • If the value is greater than target, move left.
    • If the value is less than target, move down.
  • Why it works:
    • Rows increase left → right.
    • Columns increase top → bottom.

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        int m = matrix.length;
        int n = matrix[0].length;

        int row = 0;
        int col = n - 1;

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

        return false;
    }
}

⏱ Time and Space Complexity

  • Time Complexity: O(m + n)
    Worst case: we move from top-right to bottom-left.
  • Space Complexity: O(1)
    No extra space used.

✍️ Summary

  • The staircase search pattern is a must-know technique for sorted 2D matrices.
  • It’s more efficient than binary search on each row or column separately.
  • Similar sorted matrix problems:
    • lc-74 (Search a 2D Matrix)
    • lc-378 (Kth Smallest Element in a Sorted Matrix)

When rows and columns are sorted, think about combining row and column movement strategies instead of brute force search.