The O(n) Club: Edge-Walking Your Way Through 2D Matrix Search (No More Row-by-Row Regret)

The O(n) Club: Edge-Walking Your Way Through 2D Matrix Search (No More Row-by-Row Regret)

⚡ TL;DR

Don’t let a sorted 2D matrix make you its minion. Start at the bottom-left, move up or right, and zero in on your target in O(m+n). Here’s your Java espresso shot:

// Matrix ninja mode
public boolean searchMatrix(int[][] matrix, int target) {
    int rows = matrix.length, cols = matrix[0].length;
    int r = rows - 1, c = 0;
    while (r >= 0 && c < cols) {
        if (matrix[r][c] == target) return true;
        else if (matrix[r][c] < target) c++;
        else r--;
    }
    return false;
}

🧠 How Devs Usually Mess This Up

Classic stumbles include:

• O(mn) Brute Force: Yes, you can check every cell. No, your interviewer will not give you a hug for it.
• Binary Search Per Row: Decent, but you’re ignoring the sweet two-dimensional benefits. Why settle for half a superpower?
• 1D Flattening: Unless your matrix is literally sorted as one big line (it probably isn’t), this technique clocks in at Wrong Answers Only.

🔍 What’s Actually Going On

Imagine your matrix like a giant Sudoku board where every row and column is sorted from polite to overachiever. If you start at the bottom-left corner, each step lets you knock out either an entire row or column with just one glance. If the number’s too small, move right—things get larger. Too big, move up—numbers shrink. It’s like chasing your target through a data maze, kicking down walls as you go.

🛠️ PseudoCode

• Start at bottom-left:
  row = matrix.length - 1; col = 0;
• While in bounds:
  • If matrix[row][col] == target, return true. (You found Waldo!)
  • If matrix[row][col] < target, col++ (go right, things get spicier)
  • If matrix[row][col] > target, row-- (go up, cool things down)
• Run out of matrix? Return false and grumble in peace.

💻 The Code

public boolean searchMatrix(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
    int row = matrix.length - 1;
    int col = 0;
    while (row >= 0 && col < matrix[0].length) {
        if (matrix[row][col] == target) return true;
        else if (matrix[row][col] < target) col++;
        else row--;
    }
    return false;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Matrix is empty? You’ll get a NullPointerException faster than an intern spills coffee.
• Wrong start corner: Start at bottom-left or top-right—or get ready for maximum confusion.
• Unsorted matrix: This party trick only works when rows AND columns are sorted. Mix it up and it’s chaos.
• Space & Time: Only O(m+n) moves: you’ll reach the end (or your answer) quick, without parking lots of extra memory.

🧠 Interviewer Brain-Tattoo

“If you’re still brute-forcing sorted 2D matrices, even the matrix itself is judging you. Walk the edge. Use both orders. Don’t binary search where you can bulldoze.”