Spiral Matrix II (Fill Outward Spiral)

📋

Problem

Imagine you are designing a digital display that fills numbers in a spiral pattern starting from the top-left corner and moving outward. This pattern is common in image processing and UI animations.

Given a positive integer n, generate an n x n matrix filled with elements from 1 to n² in spiral order, starting from the top-left corner and moving clockwise outward.

1 ≤ n ≤ 1000

Edge cases: n = 1 → [[1]] single element matrixn = 2 → [[1,2],[4,3]] smallest even dimensionn = 0 → [] empty matrix (if allowed)

</>

IDE

def generateMatrix(n: int) -> list:public int[][] generateMatrix(int n)vector<vector<int>> generateMatrix(int n)function generateMatrix(n)

def generateMatrix(n):
    # Write your solution here
    pass

class Solution {
    public int[][] generateMatrix(int n) {
        // Write your solution here
        return new int[n][n];
    }
}

#include <vector>
using namespace std;

vector<vector<int>> generateMatrix(int n) {
    // Write your solution here
    return vector<vector<int>>(n, vector<int>(n, 0));
}

function generateMatrix(n) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Matrix with missing or duplicated numbersIncorrect boundary updates causing overlap or skipped cells✅ After filling each side, update boundaries: top++, bottom--, left++, right-- precisely

Wrong: Empty matrix or crash on n=0No handling for n=0 input✅ Add early return: if n == 0: return []

Wrong: Center element missing or zero in odd dimension matricesLoop termination condition excludes center cell✅ Allow filling when top == bottom and left == right before loop ends

Wrong: Time limit exceeded on large nInefficient nested loops or repeated filling✅ Implement O(n^2) spiral fill using boundary pointers and single pass per cell

✓

Test Cases

Focus on handling smallest and empty inputs correctly to unlock edge cases.

Ensure your spiral logic handles multiple layers and center elements precisely.

Optimize your solution to run efficiently on large inputs without timing out.

t1_01basic

Input3

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

⏱ Performance - must finish in 2000ms

Numbers start at 1 in the top-left, move right to 3, then down, left, and up in a spiral until the matrix is filled.

💡 Visualize the matrix boundaries shrinking as you fill numbers in a spiral.

💡 Use four pointers: top, bottom, left, right to track the current edges.

💡 Fill top row left to right, right column top to bottom, bottom row right to left, left column bottom to top, then shrink boundaries.

Why it failed: Incorrect spiral order or boundary updates cause wrong matrix. Fix by correctly updating top, bottom, left, right after each side fill.

✓ Correct spiral traversal and boundary shrinking implemented.

t1_02basic

Input4

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

⏱ Performance - must finish in 2000ms

4x4 matrix filled in spiral order starting from 1 at top-left moving clockwise outward.

💡 Check that your loops correctly handle the inner layers after outer layers are filled.

💡 Ensure the direction changes happen after each side is filled and boundaries are updated.

💡 Use a while loop with condition left <= right and top <= bottom to control filling.

Why it failed: Off-by-one errors in loops or boundary conditions cause missing or duplicated numbers. Fix loop ranges and boundary updates precisely.

✓ Loops and boundaries correctly handle multiple spiral layers.

t2_01edge

Input1

Expected[[1]]

⏱ Performance - must finish in 2000ms

Single element matrix, simplest spiral is just the number 1.

💡 Consider the smallest input where n=1.

💡 Your code should handle the case where top == bottom and left == right immediately.

💡 Return [[1]] directly or ensure loops handle this minimal case without error.

Why it failed: Code fails or returns empty matrix for n=1 due to incorrect loop conditions. Fix by allowing loops to run when boundaries equal.

✓ Handles single element matrix correctly.

t2_02edge

Input2

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

⏱ Performance - must finish in 2000ms

Smallest even dimension matrix, spiral fills 1 to 4 clockwise.

💡 Test smallest even dimension to verify boundary shrinking logic.

💡 Check that after filling top row and right column, bottom row and left column fill correctly.

💡 Ensure no overlap or missing cells in the 2x2 matrix.

Why it failed: Incorrect boundary updates cause overlapping or missing cells in small even matrix. Fix by carefully updating boundaries after each side.

✓ Correctly fills smallest even dimension matrix.

t2_03edge

Input0

Expected[]

⏱ Performance - must finish in 2000ms

Empty matrix for n=0, should return empty list.

💡 Check if input n=0 is allowed and handle gracefully.

💡 Return empty list immediately if n=0 to avoid errors.

💡 Avoid loops or matrix initialization when n=0.

Why it failed: Code crashes or returns non-empty for n=0 due to missing input validation. Fix by adding early return for n=0.

✓ Handles empty matrix input correctly.

t3_01corner

Input5

Expected[[1,2,3,4,5],[16,17,18,19,6],[15,24,25,20,7],[14,23,22,21,8],[13,12,11,10,9]]

⏱ Performance - must finish in 2000ms

5x5 matrix tests correct spiral filling with multiple layers and center element.

💡 Beware of off-by-one errors when filling inner layers.

💡 Check that the center element is assigned correctly after all layers.

💡 Ensure loops terminate correctly when top > bottom or left > right.

Why it failed: Center element missing or incorrect due to loop termination condition errors. Fix by allowing center fill when top == bottom and left == right.

✓ Correctly fills all layers including center element.

t3_02corner

Input6

Expected[[1,2,3,4,5,6],[20,21,22,23,24,7],[19,32,33,34,25,8],[18,31,36,35,26,9],[17,30,29,28,27,10],[16,15,14,13,12,11]]

⏱ Performance - must finish in 2000ms

6x6 matrix tests spiral filling with even dimension and multiple layers.

💡 Check that your code handles even dimension matrices with multiple layers correctly.

💡 Verify that the direction changes and boundary updates are consistent for all layers.

💡 Test that no cells are overwritten or skipped.

Why it failed: Incorrect direction or boundary update causes overwritten or skipped cells in even dimension. Fix by carefully sequencing direction changes and boundary shrinking.

✓ Correctly fills even dimension matrix with multiple layers.

t3_03corner

Input7

Expected[[1,2,3,4,5,6,7],[24,25,26,27,28,29,8],[23,40,41,42,43,30,9],[22,39,48,49,44,31,10],[21,38,47,46,45,32,11],[20,37,36,35,34,33,12],[19,18,17,16,15,14,13]]

⏱ Performance - must finish in 2000ms

7x7 matrix tests spiral filling with odd dimension and multiple layers.

💡 Test for off-by-one errors in odd dimension matrices with multiple layers.

💡 Ensure the center element is assigned correctly after all layers.

💡 Verify that boundary pointers update correctly after each spiral round.

Why it failed: Center element missing or loops run too long causing index errors. Fix by checking loop conditions and boundary updates precisely.

✓ Correctly fills odd dimension matrix with multiple layers and center.

t4_01performance

Input100

Expectednull

⏱ Performance - must finish in 2000ms

n=100, O(n^2) time complexity must complete within 2 seconds.

💡 The algorithm should run in O(n^2) time by filling each cell once.

💡 Avoid nested loops that exceed O(n^2) complexity.

💡 Use boundary pointers to limit traversal and avoid redundant work.

Why it failed: Algorithm exceeds time limit due to inefficient nested loops or repeated work. Fix by implementing O(n^2) spiral fill with boundary shrinking.

✓ Algorithm runs within time limit with O(n^2) complexity.

Practice

1. You are given an m x n matrix. If an element is 0, you must set its entire row and column to 0 in-place without using extra space proportional to the matrix size. Which approach guarantees an optimal solution with O(1) additional space?

easy

A. Use a greedy approach that zeroes rows and columns immediately when a zero is found during iteration.

B. Use a brute force approach by creating a separate matrix to mark zero positions and then update the original matrix.

C. Use dynamic programming to store zero positions and propagate zeroes through the matrix.

D. Use the first row and first column of the matrix as flags to mark which rows and columns should be zeroed, then update the matrix accordingly.

Solution

1. Step 1: Understand space constraints

   The problem requires in-place modification with O(1) extra space, so approaches using extra matrices or arrays are not optimal.

2. Step 2: Identify the flagging technique

   Using the first row and first column as markers allows tracking which rows and columns to zero without extra space, enabling a single pass update.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   First row/column flagging is a classic O(1) space solution [OK]

Hint: Use matrix edges as flags to save space [OK]

Common Mistakes:

• Zeroing rows/columns immediately loses info about other zeros
• Using extra space arrays violates O(1) space constraint
• Greedy zeroing fails when zeros appear after initial zeroing

2. Consider the following code that transposes a square matrix in-place:

def transpose(matrix):
    n = len(matrix)
    if n == 1:
        return
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
transpose(mat)
print(mat)

What is the value of mat[1][2] after the function call?

easy

A. 8

B. 6

C. 4

D. 5

Solution

1. Step 1: Trace swaps affecting mat[1][2]

   Initially, mat[1][2] = 6. The swap occurs when i=1, j=2 swapping mat[1][2] and mat[2][1]. mat[2][1] is 8.

2. Step 2: After swap, mat[1][2] becomes 8

   Thus, mat[1][2] = 8 after transpose.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Swapping upper triangle elements swaps mat[1][2] with mat[2][1] correctly [OK]

Hint: Trace swaps only in upper triangle [OK]

Common Mistakes:

• Confusing indices i and j during swap
• Off-by-one errors in loops
• Assuming mat[1][2] remains unchanged

3. Identify the bug in the following code that attempts to transpose a square matrix in-place:

def transpose(matrix):
    n = len(matrix)
    for i in range(n):
        for j in range(n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

What is the issue?

medium

A. The inner loop should start from j = i + 1 to avoid swapping elements twice.

B. The outer loop should start from i = 1 instead of 0.

C. The swap operation should use a temporary variable instead of tuple unpacking.

D. The function should return the matrix after transposition.

Solution

1. Step 1: Analyze loop ranges

   Both loops run from 0 to n-1, causing each pair to be swapped twice, reverting to original matrix.

2. Step 2: Correct loop bounds

   Starting inner loop from j = i + 1 ensures each pair is swapped only once, fixing the bug.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Swapping twice cancels changes, so adjusting inner loop start fixes it [OK]

Hint: Swap only upper triangle elements once [OK]

Common Mistakes:

• Swapping entire matrix causing double swaps
• Incorrect loop bounds leading to index errors
• Unnecessary return statements

4. Suppose the Game of Life rules are modified so that cells can be in one of three states: dead, alive, or dormant, and the next state depends on neighbors' states with more complex transitions. Which modification to the in-place encoding approach is necessary to correctly update the board?

hard

A. Use a larger integer encoding scheme with more states to represent current and next states simultaneously.

B. Switch to copying the entire board each iteration to avoid encoding complexity.

C. Update cells immediately without encoding since more states simplify neighbor counting.

D. Ignore dormant state neighbors during counting to reduce complexity.

Solution

1. Step 1: Understand the need for more states

   With three possible states and complex transitions, encoding must represent both current and next states simultaneously.

2. Step 2: Choose encoding approach

   Using a larger integer encoding scheme (e.g., 6 or more states) allows in-place updates without losing original state info.

3. Step 3: Reject naive approaches

   Copying the board increases space; immediate updates corrupt neighbor info; ignoring dormant neighbors breaks rules.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   More states require richer encoding to preserve info [OK]

Hint: More states require more encoding bits, not naive copying [OK]

Common Mistakes:

• Switching to copying board wastes space
• Immediate updates corrupt neighbor counts
• Ignoring certain neighbors breaks rules

5. Suppose you want to output the spiral order of a matrix but now the matrix can contain negative numbers and zero, and you want to skip all zeros during traversal. Which modification to the optimal boundary shrinking algorithm correctly handles this variant without revisiting elements or breaking order?

hard

A. Add a visited matrix to mark skipped zeros and continue traversal using direction vectors.

B. Modify the boundary shrinking algorithm to skip zeros during appending but still shrink boundaries normally.

C. Use a brute force nested loop with boundary checks and skip zeros when appending elements.

D. Traverse the matrix in spiral order but collect only non-zero elements, ignoring zeros without changing traversal.

Solution

1. Step 1: Understand the challenge of skipping zeros

   Skipping zeros means some elements are not appended, but traversal must still visit all cells exactly once without repeats.

2. Step 2: Why boundary shrinking alone fails

   Boundary shrinking assumes all elements are appended; skipping zeros breaks this assumption causing incorrect boundaries or missed elements.

3. Step 3: Using a visited matrix with direction vectors

   Tracking visited cells allows skipping zeros safely while continuing traversal correctly without revisiting or missing elements.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Visited matrix ensures correct traversal despite skipping zeros [OK]

Hint: Skipping elements breaks boundary assumptions; track visited cells [OK]

Common Mistakes:

• Skipping zeros but shrinking boundaries as usual causing missed elements
• Ignoring visited tracking leading to infinite loops or repeats
• Using brute force which is inefficient