Searching in a Sorted 2D Matrix | Leetcode 2D Matrix

"Given a sorted 2D matrix (each row and column is sorted), and a target number, determine if the number exists in the matrix."

At first glance, it looked simple. But as always, the devil is in the details. Here’s how my thought process evolved.

Step 1: Brute Force - The Obvious Start

Like any beginner, my first thought was simple: “Why not just check every single cell?”

So I wrote this:

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == target) {
                    return true;
                }
            }
        }
        return false;
    }
}

Correctness: 100%
Performance: Disaster.

This works fine for small matrices. But for large inputs, the time complexity is O(n*m) which means scanning every single element. Clearly not scalable.

Step 2: Can We Use Sorting? (Binary Search on Rows)

The matrix was sorted row-wise. That clicked something in my head: “Hey, sorted → binary search!”

So instead of scanning linearly, I applied binary search to each row:

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        for (int i = 0; i < matrix.length; i++) {
            int low = 0, high = matrix[0].length - 1;
            while (low <= high) {
                int mid = low + (high - low) / 2;
                if (matrix[i][mid] == target) return true;
                else if (matrix[i][mid] < target) low = mid + 1;
                else high = mid - 1;
            }
        }
        return false;
    }
}

This reduced the time to O(n log m) - binary searching every row.
It felt like progress, but still, I wasn’t happy.

Why? Because I was repeating binary search n times. Surely there had to be a smarter way.

Step 3: The Aha Moment - Staircase Search

Then it hit me. The matrix wasn’t just row-wise sorted. It was also column-wise sorted.

That means:

• If I stand at the top-right corner, I have the largest element in the row and the smallest element in the column.

• If my current element is too big → I can safely move left (since everything below is even bigger).

• If my current element is too small → I can safely move down (since everything left is smaller).

This movement felt like walking down stairs - hence the name Staircase Search.

Here’s the clean solution:

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int row = 0, col = matrix[0].length - 1;

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

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

No more brute force. No more redundant binary searches. Just a clean, efficient walk through the matrix.

Complexity Recap

Final Thoughts

This problem taught me something important:

Sometimes the most optimal solution isn’t about brute force or heavy algorithms — it’s about observing the data’s structure and moving smartly.

The staircase search was my “aha moment” here. It’s not just optimal; it’s also elegant.