Spiral Matrix (Read Outward Spiral)

📋

Problem

Imagine you have a photo album arranged in a square grid, and you want to view the pictures starting from the outermost frame and moving inward in a spiral fashion.

Given an m x n matrix, return all elements of the matrix in spiral order, starting from the top-left corner and moving clockwise outward to inward.

1 ≤ m, n ≤ 10^3Matrix elements can be any integer

Edge cases: Single row matrix → output is the row itselfSingle column matrix → output is the column itselfMatrix with one element → output is that element

</>

IDE

def spiralOrder(matrix: list[list[int]]) -> list[int]:public List<Integer> spiralOrder(int[][] matrix)vector<int> spiralOrder(vector<vector<int>>& matrix)function spiralOrder(matrix)

def spiralOrder(matrix):
    # Write your solution here
    pass

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
using namespace std;

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    // Write your solution here
    return {};
}

function spiralOrder(matrix) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Duplicates or missing elements in outputIncorrect boundary updates or loop conditions causing repeated or skipped traversal of edges.✅ After traversing each edge, update the corresponding boundary pointer and check loop conditions with <= to avoid overlap.

Wrong: Empty output for non-empty matrixNot handling empty matrix or single element matrix input properly, causing early return or no traversal.✅ Add guard clause: if not matrix or not matrix[0]: return []. Ensure loop runs at least once for single element.

Wrong: Output order incorrect for rectangular matricesOff-by-one errors in loops or incorrect traversal order of edges.✅ Traverse edges in order: top row left to right, right column top to bottom, bottom row right to left, left column bottom to top. Use <= in loop conditions.

Wrong: TLE on large inputsUsing exponential or nested loops beyond O(m*n) complexity.✅ Implement boundary shrinking with four pointers and single pass traversal to achieve O(m*n) time complexity.

✓

Test Cases

Try testing your code with empty and single-element matrices to catch base case bugs.

Test with single row and single column matrices to catch boundary traversal bugs.

Optimize your solution to run in O(m*n) time to handle large matrices efficiently.

t1_01basic

Input{"matrix":[[1,2,3],[4,5,6],[7,8,9]]}

Expected[1,2,3,6,9,8,7,4,5]

⏱ Performance - must finish in 2000ms

Traverse top row left to right, right column top to bottom, bottom row right to left, left column bottom to top, then inward to the center.

💡 Visualize the matrix boundaries shrinking as you traverse.

💡 Use four pointers: top, bottom, left, right to track boundaries.

💡 Iterate while left <= right and top <= bottom, traversing edges in order.

Why it failed: Output incorrect - likely boundary pointers not updated correctly or loop conditions wrong. Fix by ensuring top, bottom, left, right update after each edge traversal and loop condition is while left <= right and top <= bottom.

✓ Correct spiral traversal with proper boundary updates.

t1_02basic

Input{"matrix":[[1,2,3,4],[5,6,7,8],[9,10,11,12]]}

Expected[1,2,3,4,8,12,11,10,9,5,6,7]

⏱ Performance - must finish in 2000ms

Traverse outer edges clockwise then move inward to remaining elements.

💡 Check traversal order: top row, right column, bottom row, left column.

💡 Adjust boundaries after each edge to avoid duplicates.

💡 Stop when top > bottom or left > right to prevent over-traversal.

Why it failed: Incorrect output - possibly missing or duplicating elements due to incorrect boundary checks or loop conditions. Fix by carefully updating boundaries and checking conditions before each edge traversal.

✓ Spiral traversal correctly handles rectangular matrices.

t2_01edge

Input{"matrix":[]}

Expected[]

⏱ Performance - must finish in 2000ms

Empty matrix input should return empty list.

💡 Check if matrix or matrix[0] is empty before processing.

💡 Return empty list immediately if no elements.

💡 Avoid index errors by validating input size first.

Why it failed: Code crashes or returns non-empty output on empty input. Fix by adding a guard clause: if not matrix or not matrix[0]: return []. This is the empty input test.

✓ Handles empty matrix input gracefully.

t2_02edge

Input{"matrix":[[42]]}

Expected[42]

⏱ Performance - must finish in 2000ms

Single element matrix returns that element.

💡 For single element, traversal is just that element.

💡 Boundary pointers top=bottom=left=right=0 should handle this.

💡 Ensure loop runs at least once for single element.

Why it failed: Output empty or incorrect for single element matrix. Fix by ensuring loop condition allows processing when top == bottom and left == right. This is the single element test.

✓ Correctly returns single element.

t2_03edge

Input{"matrix":[[1,2,3,4,5]]}

Expected[1,2,3,4,5]

⏱ Performance - must finish in 2000ms

Single row matrix returns the row itself.

💡 When top == bottom, only traverse left to right once.

💡 Avoid traversing bottom or left edges if boundaries overlap.

💡 Check loop conditions carefully for single row.

Why it failed: Output duplicates or misses elements in single row. Fix by checking if top == bottom before traversing bottom row and skip if so. This is the single row test.

✓ Correctly handles single row matrix.

t3_01corner

Input{"matrix":[[1],[2],[3],[4],[5]]}

Expected[1,2,3,4,5]

⏱ Performance - must finish in 2000ms

Single column matrix returns the column itself.

💡 When left == right, traverse top to bottom only once.

💡 Avoid traversing right or bottom edges if boundaries overlap.

💡 Check loop conditions carefully for single column.

Why it failed: Output duplicates or misses elements in single column. Fix by checking if left == right before traversing right column and skip if so. This is the single column test.

✓ Correctly handles single column matrix.

t3_02corner

Input{"matrix":[[1,2],[3,4]]}

Expected[1,2,4,3]

⏱ Performance - must finish in 2000ms

Small square matrix tests correct boundary shrinking and no duplicates.

💡 Check that after traversing top and right edges, bottom and left edges are still valid.

💡 Avoid double counting elements when boundaries cross.

💡 Update boundaries carefully after each edge.

Why it failed: Output duplicates or misses elements due to incorrect boundary updates or loop conditions. Fix by ensuring after each edge traversal boundaries are updated and checked before next edge. This is the small square matrix test.

✓ Correctly handles small square matrix.

t3_03corner

Input{"matrix":[[1,2,3],[4,5,6]]}

Expected[1,2,3,6,5,4]

⏱ Performance - must finish in 2000ms

Rectangular matrix with more columns than rows tests boundary conditions.

💡 Ensure loop condition uses <= for boundaries to include last elements.

💡 Traverse edges in correct order and update boundaries after each.

💡 Check for off-by-one errors in loops.

Why it failed: Output missing elements or wrong order due to off-by-one errors in loops or boundary updates. Fix by using <= in loop conditions and updating boundaries properly. This is the rectangular matrix test.

✓ Correctly handles rectangular matrix with more columns.

t4_01performance

Input{"_description":"n=1000 at constraint boundary - executor generates this input"}

Expectednull

⏱ Performance - must finish in 2000ms

Matrix size 1000x1000 requires O(m*n) = 1,000,000 operations; must complete within 2 seconds.

💡 Algorithm must be O(m*n) time complexity.

💡 Avoid nested loops that exceed O(m*n).

💡 Use boundary shrinking technique to traverse efficiently.

Why it failed: TLE due to algorithm exceeding O(m*n) complexity, likely using exponential or nested loops incorrectly. Fix by implementing boundary shrinking with four pointers and single pass traversal.

✓ Algorithm runs in O(m*n) time and completes within time limit.

Practice

1. You are given a 2D matrix and asked to find the maximum sum of a pattern shaped like an hourglass (3 elements on top row, 1 in the middle, 3 on bottom row). Which approach guarantees an optimal solution with O(n*m) time complexity and O(1) extra space?

easy

A. Use a greedy approach to pick the largest elements in each row independently.

B. Use a brute force approach by checking every possible 3x3 submatrix sum.

C. Use dynamic programming to store maximum sums of smaller subproblems and combine them.

D. Use a sliding window technique that updates the hourglass sum by adding and removing only the changed elements when moving right.

Solution

1. Step 1: Understand the hourglass pattern

   The hourglass consists of 7 fixed positions in a 3x3 block, not the entire 3x3 matrix.

2. Step 2: Recognize the sliding window optimization

   Sliding window updates the sum by removing left column elements and adding right column elements, achieving O(n*m) time and O(1) space.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sliding window updates sums efficiently without recomputing full sums [OK]

Hint: Sliding window updates sums incrementally [OK]

Common Mistakes:

• Confusing hourglass with full 3x3 submatrix sum
• Thinking DP is needed
• Assuming greedy works for max sum pattern

2. You are given an n x n matrix representing an image. The task is to rotate the image by 90 degrees clockwise in-place, without using extra space. Which of the following approaches guarantees an optimal in-place solution with O(1) extra space and O(n²) time complexity?

easy

A. Perform a layer-by-layer rotation by swapping four elements at a time in-place for each layer of the matrix.

B. Apply a dynamic programming approach to store intermediate rotations and build the final rotated matrix.

C. Use a brute force approach by creating a new matrix and copying elements to their rotated positions.

D. Transpose the matrix and then reverse each column to achieve the rotation.

Solution

1. Step 1: Understand the problem constraints

   The problem requires rotating the matrix in-place with O(1) extra space and O(n²) time.

2. Step 2: Evaluate approaches

   Brute force uses extra space, DP is unrelated, and transposing then reversing columns rotates counterclockwise, not clockwise. Layer-by-layer four-way swaps correctly rotate clockwise in-place.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Layer-by-layer swaps rotate in-place with correct direction and complexity [OK]

Hint: Layer-by-layer four-way swaps rotate in-place clockwise [OK]

Common Mistakes:

• Confusing transpose+reverse columns with clockwise rotation
• Using extra space when in-place is required

3. Given the following code snippet to generate an n x n spiral matrix, what is the value of matrix[1][1] after the function completes when n = 3?

easy

A. 5

B. 9

C. 7

D. 3

Solution

1. Step 1: Trace filling the matrix for n=3

   First row (top=0): fill 1,2,3; then right column (right=2): fill 4,5; then bottom row (bottom=2): fill 6,7; then left column (left=0): fill 8; then top row (top=1): fill 9.

2. Step 2: Identify matrix[1][1]

   After filling outer layers, the center cell matrix[1][1] is assigned the number 5 during the downward fill.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Center cell is the 5th number filled in spiral order [OK]

Hint: Center cell in 3x3 spiral is 5 [OK]

Common Mistakes:

• Confusing indices or direction order
• Off-by-one errors in loops
• Miscounting the fill sequence

4. The following code attempts to rotate an n x n matrix by 90 degrees clockwise in-place. Identify the line containing the subtle bug that causes incorrect rotation.

medium

A. matrix[last][last - offset] = matrix[i][last]

B. matrix[last - offset][first] = matrix[last][last - offset]

C. matrix[i][last] = matrix[i][last]

D. matrix[first][i] = matrix[last - offset][first]

Solution

1. Step 1: Analyze the last assignment

   The last line should assign the saved top value to matrix[i][last], but it assigns matrix[i][last] to itself.

2. Step 2: Identify the fix

   Replace matrix[i][last] = matrix[i][last] with matrix[i][last] = top to complete the four-way swap correctly.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Incorrect assignment leaves matrix partially unrotated [OK]

Hint: Last assignment must restore saved top element to complete rotation [OK]

Common Mistakes:

• Forgetting to assign saved top value
• Swapping elements twice causing corruption

5. Suppose you want to generate a spiral matrix but now the matrix size n can be very large and you want to generate the spiral matrix lazily (on-demand) without storing the entire matrix in memory. Which modification to the algorithm is most suitable?

hard

A. Use recursion to generate submatrices and merge results

B. Use a formula to compute the value at any (row, col) position directly without simulation

C. Precompute the entire matrix and stream rows as needed

D. Simulate the spiral traversal with boundary shrinking but store only current boundaries and output values on the fly

Solution

1. Step 1: Understand memory constraints

   Storing the entire matrix is infeasible for large n, so we need an approach that generates values on demand.

2. Step 2: Evaluate options

   Precomputing (C) uses too much memory. Direct formula (B) is complex and non-trivial for spiral order. Recursion (D) adds overhead and complexity.

3. Step 3: Choose simulation with minimal state

   Simulating spiral traversal with boundary shrinking and outputting values as generated uses O(n) space for boundaries and O(1) extra space, suitable for lazy generation.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Simulation with minimal state supports lazy generation [OK]

Hint: Lazy generation needs minimal state, not full precomputation [OK]

Common Mistakes:

• Assuming direct formula for spiral indices is trivial
• Trying to precompute full matrix defeats memory goal
• Using recursion increases space and complexity unnecessarily