The O(n) Club: Search a 2D Matrix: Stop Nesting and Start Flattening

⚡ TL;DR

This sorted 2D matrix wants you to get clever, not just caffeinated. Sure, you could groan through every row and column, but a single flat binary search is peak efficiency. It works because every row starts after the last, so the whole thing is basically a 1D array in cosplay.

🧠 How Devs Usually Mess This Up

Classic dev move: see a 2D matrix, deploy two loops or a two-step binary search (“first find the row, then the column!”). Or—let’s be honest—just smother it with nested for-loops. O(mn) later, you start questioning your career choices. Forgetting the problem’s rules about each row picking up right where the last left off is the most expensive oversight you can make. Don’t bring a sieve to a sorted spreadsheet party.

🔍 What’s Actually Going On

The catch (and the charm): Each row’s first item is bigger than the previous row’s last, so all numbers are sorted, left to right, top to bottom. That means you can pretend the matrix is a single huge array. Solve it with normal binary search, using a little arithmetic to bounce between 1D and 2D worlds. (It’s like looking for your reserved movie seat, but actually following the row and seat number instead of interrogating every usher.)

🛠️ PseudoCode

If it wasn’t there, return false.

Compare:

if (matrix[row][col] == target) return true;
if (matrix[row][col] < target) left = mid + 1;
else right = mid - 1;

Standard binary shenanigans.

Find mid and map it:

int mid = left + (right - left) / 2;
int row = mid / cols;
int col = mid % cols;

Division and modulo: nerdy, but crucial.

While left <= right, rinse and repeat:

while (left <= right) {...}

Initialize left & right boundaries.

int left = 0;
int right = (rows * cols) - 1;

Just like 1D, but with more imagination.

Handle the null and empty training-wheels.

if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;

Reject chaos early.

💻 The Code

public boolean searchMatrix(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return false;
    }
    int m = matrix.length, n = matrix[0].length;
    int left = 0, right = m * n - 1;
    while (left &lt;= right) {
        int mid = left + (right - left) / 2;
        int row = mid / n;
        int col = mid % n;
        if (matrix[row][col] == target) {
            return true;
        } else if (matrix[row][col] &lt; target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return false;
}

⚠️ Pitfalls, Traps & Runtime Smacks

Don’t forget empty input checks! Java will absolutely not forgive matrix[0] if matrix is empty.
This trick only works for supremely sorted matrices. If only rows OR columns are sorted, you’re in the wrong blog post.
Overflow paranoia. Use left + (right - left) / 2 for mid to avoid integer overflow. (Yes, it happens. Yes, they’ll ask.)
Time/Space: O(log(mn)), unless you decide brute force is your love language.