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

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.

// Brute force special (do not show your interviewer):
for (int[] row : matrix) {
    for (int n : row) {
        if (n == target) return true;
    }
}
return false;

🧠 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

• Handle the null and empty training-wheels.

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

  Reject chaos early.
• Initialize left & right boundaries.

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

  Just like 1D, but with more imagination.
• While left <= right, rinse and repeat:

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

• 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.
• Compare:

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

  Standard binary shenanigans.
• If it wasn’t there, return false.

💻 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 <= 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] < 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.

🧠 Interviewer Brain-Tattoo

“If your 2D matrix is sorted like a librarian on Adderall, you can always flatten it and get on with your life.” (Unlike your inbox.)