The O(n) Club: Spiral Matrix — How to Spiral Without Actually Losing Your Mind

The O(n) Club: Spiral Matrix — How to Spiral Without Actually Losing Your Mind

⚡ TL;DR

Spiral Matrix: Peel the matrix like you would an overbaked cinnamon roll, layer by layer, never duplicating a bite. Brute force tries to map out visited cells with direction arrays—because sometimes we all wish Java was just a spreadsheet:

// Brute force spiral (not recommended):
List<Integer> spiralOrder(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    boolean[][] seen = new boolean[m][n];
    int[] dr = {0, 1, 0, -1};
    int[] dc = {1, 0, -1, 0};
    List<Integer> ans = new ArrayList<>();
    int r = 0, c = 0, di = 0;
    for (int i = 0; i < m * n; ++i) {
        ans.add(matrix[r][c]);
        seen[r][c] = true;
        int nr = r + dr[di], nc = c + dc[di];
        if (nr >= 0 && nr < m && nc >= 0 && nc < n && !seen[nr][nc]) {
            r = nr; c = nc;
        } else {
            di = (di + 1) % 4;
            r += dr[di]; c += dc[di];
        }
    }
    return ans;
}

🧠 How Devs Usually Mess This Up

Most devs try to herd cats with compass arrays or lose themselves in visited-checks. End result: either an infinite spiral of sadness or off-by-one errors that turn a square into some kind of bug-ridden Möbius band. Pro tip: rectangular matrices and lone rows are where the real tears start flowing.

🔍 What’s Actually Going On

Forget directions—think boundaries. The matrix isn’t a maze, it’s an onion. Peel the edges: top row, right column, bottom row, left column. Then shrink your boundaries and keep spiraling inward until there’s nothing left but tears of joy (and O(mn) glory). No need for a ‘visited’ tattoo. Just pointers that know when it’s time to move on.

🛠️ PseudoCode

• Start with: top = 0, bottom = matrix.length – 1, left = 0, right = matrix[0].length – 1.
• While top ≤ bottom and left ≤ right:
• Go left ➡️ right along top. Then: top++.
• Go top ⬇️ bottom along right. Then: right–.
• If rows left: go right ⬅️ left on bottom. Then: bottom–.
• If columns left: go bottom ⬆️ top on left. Then: left++.
• Repeat. Do not pass go. Do not revisit any cell. Escape with dignity.

💻 The Code

List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> result = new ArrayList<>();
    int m = matrix.length, n = m == 0 ? 0 : matrix[0].length;
    int top = 0, bottom = m - 1, left = 0, right = n - 1;
    while (top <= bottom && left <= right) {
        for (int col = left; col <= right; col++) result.add(matrix[top][col]);
        top++;
        for (int row = top; row <= bottom; row++) result.add(matrix[row][right]);
        right--;
        if (top <= bottom) {
            for (int col = right; col >= left; col--) result.add(matrix[bottom][col]);
            bottom--;
        }
        if (left <= right) {
            for (int row = bottom; row >= top; row--) result.add(matrix[row][left]);
            left++;
        }
    }
    return result;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Rectangular matrices: Mind your boundary updates. Overlap and you’ll double-dip like an uninvited guest at a party.
• Single row or single column: Watch your stopping conditions or get trapped forever in Java’s equivalent of the Twilight Zone.
• Time: O(mn). Space: O(1) extra (the output list is fair game). Not groundbreaking, but as reliable as a caffeinated mutex.

🧠 Interviewer Brain-Tattoo

“Fight the urge to chart directions. Just squeeze your boundaries and keep spiraling — like your dev sanity under tight deadlines.”