The O(n) Club: Rotate Image Without Losing Your Mind (LeetCode 48)

The O(n) Club: Rotate Image Without Losing Your Mind (LeetCode 48)

⚡ TL;DR

Rotate your n x n matrix 90° in-place by: (1) transposing (swap rows for columns), (2) reversing every row. Trying to sneak in a new array? Out you go.

// Bad (but classic) rookie move: wastes space
int n = matrix.length;
int[][] rotated = new int[n][n];
for (int r = 0; r < n; r++) {
    for (int c = 0; c < n; c++) {
        rotated[c][n - r - 1] = matrix[r][c];
    }
}
// The array rotated, but so did your job prospects.

🧠 How Devs Usually Mess This Up

Some developers see “rotate” and break into a cold sweat, immediately reaching for a brand new matrix. Nope, the problem wants in-place, so that solution is like showing up to a coding interview armed with an Excel spreadsheet. Common stumbles:

• Creating (and then clinging to) a second array because “memory is cheap, right?”
• Mangling indices during transpose or totally flipping the wrong way (not all spins are created equal)
• Trying clockwise, writing counterclockwise, and debugging forever—been there 🙃

🔍 What’s Actually Going On

Imagine your matrix is a stubborn sticky note and the interviewer’s hand is spinning it on the table. First: fold it in half diagonally (that’s transpose—swap [i][j] with [j][i]). Second: flip each row like the world’s lamest pancake (reverse every row). That’s how every graphics app (and Rubik’s Cube wizard) spins a square board—no extra sticky notes required.

🛠️ PseudoCode

• Step 1: Transpose
  • For every i and j > i, swap matrix[i][j] with matrix[j][i]:

  for (int i = 0; i < n; i++) {
      for (int j = i+1; j < n; j++) {
          int t = matrix[i][j];
          matrix[i][j] = matrix[j][i];
          matrix[j][i] = t;
      }
  }

💻 The Code

public void rotate(int[][] matrix) {
    int n = matrix.length;
    // Transpose
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }
    // Reverse rows
    for (int i = 0; i < n; i++) {
        int l = 0, r = n-1;
        while (l < r) {
            int temp = matrix[i][l];
            matrix[i][l] = matrix[i][r];
            matrix[i][r] = temp;
            l++;
            r--;
        }
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Space Out: If your code creates a new array, even “temporarily,” you’re out.
• Off-by-One-itis: Transpose swaps should start with j=i+1 (else, your code does a self-high-five).
• Not Square? If the input isn’t n x n, just pivot your chair and walk away.
• Your Array Will Change: It’s all in-place, so it’ll mutate like leftover JavaScript on a Friday.
• Performance: O(n²) time and O(1) space—unless you count how much your brain will rotate writing good test cases.

🧠 Interviewer Brain-Tattoo

“Make a copy and your offer copy-pastes… straight into the trash bin.”