Spiral Matrix II (Fill Outward Spiral)

🎯

Spiral Matrix II (Fill Outward Spiral)

mediumMATRIXAmazonMicrosoftGoogle

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.

💡 This problem requires careful control of matrix boundaries and directions. Beginners often struggle because it involves multiple pointers and conditions to correctly fill the matrix in spiral order without overwriting or missing cells.

📋

Problem Statement

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

💡

Example

Input"3"

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

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.

• n = 1 → [[1]] single element matrix
• n = 2 → [[1,2],[4,3]] smallest even dimension
• n = 0 → [] empty matrix (if allowed)
• n = 10 → large matrix to test performance and boundary correctness

⚠️

Common Mistakes

Not updating boundaries correctly after each direction

Overwrites cells or infinite loops

✅ Carefully update top, bottom, left, right after filling each side

Forgetting to check boundary conditions before filling bottom or left sides

Index out of range errors or overwriting

✅ Add checks like if top ≤= bottom and if left ≤= right before filling those sides

Incorrect direction cycling or off-by-one errors in loops

Wrong spiral pattern or missed cells

✅ Use modulo arithmetic for direction index and carefully set loop ranges

Not initializing the matrix properly or using wrong dimensions

Runtime errors or incorrect output

✅ Initialize n x n matrix with zeros before filling

Using recursion or complex data structures unnecessarily

Unnecessary complexity and possible stack overflow

✅ Use iterative approach with boundaries and directions for clarity and efficiency

🧠

Brute Force (Simulate Spiral with Boundary Checks)

💡 This approach exists to build intuition by simulating the spiral filling step-by-step, which helps beginners understand the problem deeply before optimizing.

Intuition

We simulate the spiral by maintaining four boundaries (top, bottom, left, right) and fill the matrix layer by layer, moving right, down, left, and up until all cells are filled.

Algorithm

1. Initialize an n x n matrix with zeros.
2. Set four pointers: top, bottom, left, right to track current boundaries.
3. Use a counter from 1 to n² to fill the matrix.
4. Fill the matrix in four directions: left to right, top to bottom, right to left, bottom to top, shrinking boundaries after each direction until all numbers are filled.

💡 The challenge is to carefully update boundaries and directions to avoid overwriting cells or going out of bounds.

</>

Code

def generateMatrix(n):
    matrix = [[0]*n for _ in range(n)]
    left, right = 0, n - 1
    top, bottom = 0, n - 1
    num = 1
    while left <= right and top <= bottom:
        for col in range(left, right + 1):
            matrix[top][col] = num
            num += 1
        top += 1
        for row in range(top, bottom + 1):
            matrix[row][right] = num
            num += 1
        right -= 1
        if top <= bottom:
            for col in range(right, left - 1, -1):
                matrix[bottom][col] = num
                num += 1
            bottom -= 1
        if left <= right:
            for row in range(bottom, top - 1, -1):
                matrix[row][left] = num
                num += 1
            left += 1
    return matrix

# Driver code
if __name__ == '__main__':
    n = 3
    result = generateMatrix(n)
    for row in result:
        print(row)

Line Notes

matrix = [[0]*n for _ in range(n)]Initialize an empty n x n matrix to fill numbers

left, right = 0, n - 1Set initial horizontal boundaries for spiral traversal

top, bottom = 0, n - 1Set initial vertical boundaries for spiral traversal

while left <= right and top <= bottom:Continue filling while boundaries are valid

for col in range(left, right + 1):Fill top row from left to right

top += 1Shrink top boundary after filling top row

for row in range(top, bottom + 1):Fill right column from top to bottom

right -= 1Shrink right boundary after filling right column

if top <= bottom:Check if bottom row is still valid before filling

for col in range(right, left - 1, -1):Fill bottom row from right to left

bottom -= 1Shrink bottom boundary after filling bottom row

if left <= right:Check if left column is still valid before filling

for row in range(bottom, top - 1, -1):Fill left column from bottom to top

left += 1Shrink left boundary after filling left column

import java.util.*;
public class SpiralMatrixII {
    public static int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        int left = 0, right = n - 1;
        int top = 0, bottom = n - 1;
        int num = 1;
        while (left <= right && top <= bottom) {
            for (int col = left; col <= right; col++) {
                matrix[top][col] = num++;
            }
            top++;
            for (int row = top; row <= bottom; row++) {
                matrix[row][right] = num++;
            }
            right--;
            if (top <= bottom) {
                for (int col = right; col >= left; col--) {
                    matrix[bottom][col] = num++;
                }
                bottom--;
            }
            if (left <= right) {
                for (int row = bottom; row >= top; row--) {
                    matrix[row][left] = num++;
                }
                left++;
            }
        }
        return matrix;
    }

    public static void main(String[] args) {
        int n = 3;
        int[][] result = generateMatrix(n);
        for (int[] row : result) {
            System.out.println(Arrays.toString(row));
        }
    }
}

Line Notes

int[][] matrix = new int[n][n];Create an empty n x n matrix to fill

int left = 0, right = n - 1;Initialize horizontal boundaries

int top = 0, bottom = n - 1;Initialize vertical boundaries

while (left <= right && top <= bottom)Loop until boundaries cross

for (int col = left; col <= right; col++)Fill top row left to right

top++;Move top boundary down after filling

for (int row = top; row <= bottom; row++)Fill right column top to bottom

right--;Move right boundary left after filling

if (top <= bottom)Check bottom row validity before filling

for (int col = right; col >= left; col--)Fill bottom row right to left

bottom--;Move bottom boundary up after filling

if (left <= right)Check left column validity before filling

for (int row = bottom; row >= top; row--)Fill left column bottom to top

left++;Move left boundary right after filling

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> generateMatrix(int n) {
    vector<vector<int>> matrix(n, vector<int>(n, 0));
    int left = 0, right = n - 1;
    int top = 0, bottom = n - 1;
    int num = 1;
    while (left <= right && top <= bottom) {
        for (int col = left; col <= right; col++) {
            matrix[top][col] = num++;
        }
        top++;
        for (int row = top; row <= bottom; row++) {
            matrix[row][right] = num++;
        }
        right--;
        if (top <= bottom) {
            for (int col = right; col >= left; col--) {
                matrix[bottom][col] = num++;
            }
            bottom--;
        }
        if (left <= right) {
            for (int row = bottom; row >= top; row--) {
                matrix[row][left] = num++;
            }
            left++;
        }
    }
    return matrix;
}

int main() {
    int n = 3;
    vector<vector<int>> result = generateMatrix(n);
    for (auto &row : result) {
        for (int val : row) cout << val << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

vector<vector<int>> matrix(n, vector<int>(n, 0));Initialize n x n matrix with zeros

int left = 0, right = n - 1;Set horizontal boundaries

int top = 0, bottom = n - 1;Set vertical boundaries

while (left <= right && top <= bottom)Loop until boundaries cross

for (int col = left; col <= right; col++)Fill top row left to right

top++;Shrink top boundary after filling

for (int row = top; row <= bottom; row++)Fill right column top to bottom

right--;Shrink right boundary after filling

if (top <= bottom)Check bottom row validity before filling

for (int col = right; col >= left; col--)Fill bottom row right to left

bottom--;Shrink bottom boundary after filling

if (left <= right)Check left column validity before filling

for (int row = bottom; row >= top; row--)Fill left column bottom to top

left++;Shrink left boundary after filling

function generateMatrix(n) {
    const matrix = Array.from({ length: n }, () => Array(n).fill(0));
    let left = 0, right = n - 1;
    let top = 0, bottom = n - 1;
    let num = 1;
    while (left <= right && top <= bottom) {
        for (let col = left; col <= right; col++) {
            matrix[top][col] = num++;
        }
        top++;
        for (let row = top; row <= bottom; row++) {
            matrix[row][right] = num++;
        }
        right--;
        if (top <= bottom) {
            for (let col = right; col >= left; col--) {
                matrix[bottom][col] = num++;
            }
            bottom--;
        }
        if (left <= right) {
            for (let row = bottom; row >= top; row--) {
                matrix[row][left] = num++;
            }
            left++;
        }
    }
    return matrix;
}

// Driver code
const n = 3;
const result = generateMatrix(n);
result.forEach(row => console.log(row));

Line Notes

const matrix = Array.from({ length: n }, () => Array(n).fill(0));Create empty n x n matrix filled with zeros

let left = 0, right = n - 1;Initialize horizontal boundaries

let top = 0, bottom = n - 1;Initialize vertical boundaries

while (left <= right && top <= bottom)Loop until boundaries cross

for (let col = left; col <= right; col++)Fill top row left to right

top++;Move top boundary down after filling

for (let row = top; row <= bottom; row++)Fill right column top to bottom

right--;Move right boundary left after filling

if (top <= bottom)Check bottom row validity before filling

for (let col = right; col >= left; col--)Fill bottom row right to left

bottom--;Move bottom boundary up after filling

if (left <= right)Check left column validity before filling

for (let row = bottom; row >= top; row--)Fill left column bottom to top

left++;Move left boundary right after filling

⏱

Complexity

TimeO(n^2)

SpaceO(n^2)

We fill each cell exactly once in the n x n matrix, so time and space are proportional to n squared.

💡 For n=10, this means 100 operations to fill the matrix, which is efficient enough for typical interview constraints.

Interview Verdict: Accepted

This approach is efficient and clear, making it a solid solution for interviews where clarity and correctness matter.

🧠

Directional Simulation with Direction Vectors

💡 This approach uses direction vectors to simplify movement logic, reducing code duplication and making the spiral traversal more elegant.

Intuition

Instead of writing separate loops for each direction, use a direction array to cycle through right, down, left, and up movements, changing direction when hitting boundaries or filled cells.

Algorithm

1. Initialize an n x n matrix with zeros.
2. Define direction vectors for right, down, left, and up movements.
3. Start at the top-left cell and move in the current direction.
4. If the next cell is out of bounds or already filled, turn right (change direction).
5. Continue until all cells are filled.

💡 This approach abstracts direction changes, avoiding repetitive code blocks for each direction.

</>

Code

def generateMatrix(n):
    matrix = [[0]*n for _ in range(n)]
    directions = [(0,1),(1,0),(0,-1),(-1,0)]  # right, down, left, up
    dir_idx = 0
    row = col = 0
    for num in range(1, n*n + 1):
        matrix[row][col] = num
        dr, dc = directions[dir_idx]
        r, c = row + dr, col + dc
        if r < 0 or r >= n or c < 0 or c >= n or matrix[r][c] != 0:
            dir_idx = (dir_idx + 1) % 4
            dr, dc = directions[dir_idx]
            r, c = row + dr, col + dc
        row, col = r, c
    return matrix

# Driver code
if __name__ == '__main__':
    n = 3
    result = generateMatrix(n)
    for row in result:
        print(row)

Line Notes

directions = [(0,1),(1,0),(0,-1),(-1,0)]Define movement vectors for right, down, left, up

dir_idx = 0Start moving right initially

for num in range(1, n*n + 1):Fill numbers from 1 to n squared

matrix[row][col] = numAssign current number to current cell

if r < 0 or r >= n or c < 0 or c >= n or matrix[r][c] != 0:Check if next cell is invalid or already filled

dir_idx = (dir_idx + 1) % 4Change direction clockwise

row, col = r, cMove to next valid cell

import java.util.*;
public class SpiralMatrixII {
    public static int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        int[][] directions = {{0,1},{1,0},{0,-1},{-1,0}};
        int dirIdx = 0;
        int row = 0, col = 0;
        for (int num = 1; num <= n*n; num++) {
            matrix[row][col] = num;
            int dr = directions[dirIdx][0], dc = directions[dirIdx][1];
            int r = row + dr, c = col + dc;
            if (r < 0 || r >= n || c < 0 || c >= n || matrix[r][c] != 0) {
                dirIdx = (dirIdx + 1) % 4;
                dr = directions[dirIdx][0];
                dc = directions[dirIdx][1];
                r = row + dr;
                c = col + dc;
            }
            row = r;
            col = c;
        }
        return matrix;
    }

    public static void main(String[] args) {
        int n = 3;
        int[][] result = generateMatrix(n);
        for (int[] row : result) {
            System.out.println(Arrays.toString(row));
        }
    }
}

Line Notes

int[][] directions = {{0,1},{1,0},{0,-1},{-1,0}};Store direction vectors for spiral movement

int dirIdx = 0;Start moving right

for (int num = 1; num <= n*n; num++)Fill numbers from 1 to n squared

matrix[row][col] = num;Fill current cell with number

if (r < 0 || r >= n || c < 0 || c >= n || matrix[r][c] != 0)Check if next cell is invalid or filled

dirIdx = (dirIdx + 1) % 4;Rotate direction clockwise

row = r; col = c;Move to next cell

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> generateMatrix(int n) {
    vector<vector<int>> matrix(n, vector<int>(n, 0));
    vector<pair<int,int>> directions = {{0,1},{1,0},{0,-1},{-1,0}};
    int dirIdx = 0;
    int row = 0, col = 0;
    for (int num = 1; num <= n*n; num++) {
        matrix[row][col] = num;
        int dr = directions[dirIdx].first, dc = directions[dirIdx].second;
        int r = row + dr, c = col + dc;
        if (r < 0 || r >= n || c < 0 || c >= n || matrix[r][c] != 0) {
            dirIdx = (dirIdx + 1) % 4;
            dr = directions[dirIdx].first;
            dc = directions[dirIdx].second;
            r = row + dr;
            c = col + dc;
        }
        row = r;
        col = c;
    }
    return matrix;
}

int main() {
    int n = 3;
    vector<vector<int>> result = generateMatrix(n);
    for (auto &row : result) {
        for (int val : row) cout << val << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

vector<pair<int,int>> directions = {{0,1},{1,0},{0,-1},{-1,0}};Store direction vectors for spiral traversal

int dirIdx = 0;Start moving right

for (int num = 1; num <= n*n; num++)Fill numbers from 1 to n squared

matrix[row][col] = num;Assign current number to current cell

if (r < 0 || r >= n || c < 0 || c >= n || matrix[r][c] != 0)Check if next cell is invalid or already filled

dirIdx = (dirIdx + 1) % 4;Change direction clockwise

row = r; col = c;Move to next valid cell

function generateMatrix(n) {
    const matrix = Array.from({ length: n }, () => Array(n).fill(0));
    const directions = [[0,1],[1,0],[0,-1],[-1,0]];
    let dirIdx = 0;
    let row = 0, col = 0;
    for (let num = 1; num <= n*n; num++) {
        matrix[row][col] = num;
        let dr = directions[dirIdx][0], dc = directions[dirIdx][1];
        let r = row + dr, c = col + dc;
        if (r < 0 || r >= n || c < 0 || c >= n || matrix[r][c] !== 0) {
            dirIdx = (dirIdx + 1) % 4;
            dr = directions[dirIdx][0];
            dc = directions[dirIdx][1];
            r = row + dr;
            c = col + dc;
        }
        row = r;
        col = c;
    }
    return matrix;
}

// Driver code
const n = 3;
const result = generateMatrix(n);
result.forEach(row => console.log(row));

Line Notes

const directions = [[0,1],[1,0],[0,-1],[-1,0]];Define direction vectors for spiral movement

let dirIdx = 0;Start moving right

for (let num = 1; num <= n*n; num++)Fill numbers from 1 to n squared

matrix[row][col] = num;Fill current cell with number

if (r < 0 || r >= n || c < 0 || c >= n || matrix[r][c] !== 0)Check if next cell is invalid or already filled

dirIdx = (dirIdx + 1) % 4;Rotate direction clockwise

row = r; col = c;Move to next cell

⏱

Complexity

TimeO(n^2)

SpaceO(n^2)

Each cell is visited exactly once, and direction changes are constant time operations.

💡 For n=10, this means 100 steps, which is efficient and easy to implement.

Interview Verdict: Accepted

This approach is elegant and often preferred for its clean logic and maintainability.

🧠

In-Place Boundary Shrinking with Direction Indexing

💡 This approach optimizes the boundary shrinking logic by using a direction index and boundary variables, combining clarity and efficiency.

Intuition

We keep track of four boundaries and a direction index to fill the matrix in a spiral, updating boundaries and direction index as we complete each side.

Algorithm

1. Initialize an n x n matrix with zeros.
2. Set boundaries: top, bottom, left, right.
3. Set direction index to 0 representing right, down, left, up.
4. Iterate from 1 to n², filling cells and moving in the current direction.
5. When hitting a boundary, update the boundary and change direction index.
6. Repeat until all cells are filled.

💡 This approach balances explicit boundary management with direction cycling for clean code.

</>

Code

def generateMatrix(n):
    matrix = [[0]*n for _ in range(n)]
    top, bottom = 0, n - 1
    left, right = 0, n - 1
    num = 1
    direction = 0  # 0:right, 1:down, 2:left, 3:up
    while left <= right and top <= bottom:
        if direction == 0:
            for col in range(left, right + 1):
                matrix[top][col] = num
                num += 1
            top += 1
        elif direction == 1:
            for row in range(top, bottom + 1):
                matrix[row][right] = num
                num += 1
            right -= 1
        elif direction == 2:
            for col in range(right, left - 1, -1):
                matrix[bottom][col] = num
                num += 1
            bottom -= 1
        else:
            for row in range(bottom, top - 1, -1):
                matrix[row][left] = num
                num += 1
            left += 1
        direction = (direction + 1) % 4
    return matrix

# Driver code
if __name__ == '__main__':
    n = 3
    result = generateMatrix(n)
    for row in result:
        print(row)

Line Notes

top, bottom = 0, n - 1Initialize vertical boundaries

left, right = 0, n - 1Initialize horizontal boundaries

direction = 0Start moving right

while left <= right and top <= bottom:Loop until boundaries cross

if direction == 0:Fill top row left to right

top += 1Shrink top boundary after filling

elif direction == 1:Fill right column top to bottom

right -= 1Shrink right boundary after filling

elif direction == 2:Fill bottom row right to left

bottom -= 1Shrink bottom boundary after filling

else:Fill left column bottom to top

left += 1Shrink left boundary after filling

direction = (direction + 1) % 4Cycle direction clockwise

import java.util.*;
public class SpiralMatrixII {
    public static int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        int top = 0, bottom = n - 1;
        int left = 0, right = n - 1;
        int num = 1;
        int direction = 0; // 0:right,1:down,2:left,3:up
        while (left <= right && top <= bottom) {
            if (direction == 0) {
                for (int col = left; col <= right; col++) {
                    matrix[top][col] = num++;
                }
                top++;
            } else if (direction == 1) {
                for (int row = top; row <= bottom; row++) {
                    matrix[row][right] = num++;
                }
                right--;
            } else if (direction == 2) {
                for (int col = right; col >= left; col--) {
                    matrix[bottom][col] = num++;
                }
                bottom--;
            } else {
                for (int row = bottom; row >= top; row--) {
                    matrix[row][left] = num++;
                }
                left++;
            }
            direction = (direction + 1) % 4;
        }
        return matrix;
    }

    public static void main(String[] args) {
        int n = 3;
        int[][] result = generateMatrix(n);
        for (int[] row : result) {
            System.out.println(Arrays.toString(row));
        }
    }
}

Line Notes

int top = 0, bottom = n - 1;Initialize vertical boundaries

int left = 0, right = n - 1;Initialize horizontal boundaries

int direction = 0;Start moving right

while (left <= right && top <= bottom)Loop until boundaries cross

if (direction == 0)Fill top row left to right

top++;Shrink top boundary after filling

else if (direction == 1)Fill right column top to bottom

right--;Shrink right boundary after filling

else if (direction == 2)Fill bottom row right to left

bottom--;Shrink bottom boundary after filling

elseFill left column bottom to top

left++;Shrink left boundary after filling

direction = (direction + 1) % 4;Cycle direction clockwise

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> generateMatrix(int n) {
    vector<vector<int>> matrix(n, vector<int>(n, 0));
    int top = 0, bottom = n - 1;
    int left = 0, right = n - 1;
    int num = 1;
    int direction = 0; // 0:right,1:down,2:left,3:up
    while (left <= right && top <= bottom) {
        if (direction == 0) {
            for (int col = left; col <= right; col++) {
                matrix[top][col] = num++;
            }
            top++;
        } else if (direction == 1) {
            for (int row = top; row <= bottom; row++) {
                matrix[row][right] = num++;
            }
            right--;
        } else if (direction == 2) {
            for (int col = right; col >= left; col--) {
                matrix[bottom][col] = num++;
            }
            bottom--;
        } else {
            for (int row = bottom; row >= top; row--) {
                matrix[row][left] = num++;
            }
            left++;
        }
        direction = (direction + 1) % 4;
    }
    return matrix;
}

int main() {
    int n = 3;
    vector<vector<int>> result = generateMatrix(n);
    for (auto &row : result) {
        for (int val : row) cout << val << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

int top = 0, bottom = n - 1;Initialize vertical boundaries

int left = 0, right = n - 1;Initialize horizontal boundaries

int direction = 0;Start moving right

while (left <= right && top <= bottom)Loop until boundaries cross

if (direction == 0)Fill top row left to right

top++;Shrink top boundary after filling

else if (direction == 1)Fill right column top to bottom

right--;Shrink right boundary after filling

else if (direction == 2)Fill bottom row right to left

bottom--;Shrink bottom boundary after filling

elseFill left column bottom to top

left++;Shrink left boundary after filling

direction = (direction + 1) % 4;Cycle direction clockwise

function generateMatrix(n) {
    const matrix = Array.from({ length: n }, () => Array(n).fill(0));
    let top = 0, bottom = n - 1;
    let left = 0, right = n - 1;
    let num = 1;
    let direction = 0; // 0:right,1:down,2:left,3:up
    while (left <= right && top <= bottom) {
        if (direction === 0) {
            for (let col = left; col <= right; col++) {
                matrix[top][col] = num++;
            }
            top++;
        } else if (direction === 1) {
            for (let row = top; row <= bottom; row++) {
                matrix[row][right] = num++;
            }
            right--;
        } else if (direction === 2) {
            for (let col = right; col >= left; col--) {
                matrix[bottom][col] = num++;
            }
            bottom--;
        } else {
            for (let row = bottom; row >= top; row--) {
                matrix[row][left] = num++;
            }
            left++;
        }
        direction = (direction + 1) % 4;
    }
    return matrix;
}

// Driver code
const n = 3;
const result = generateMatrix(n);
result.forEach(row => console.log(row));

Line Notes

let top = 0, bottom = n - 1;Initialize vertical boundaries

let left = 0, right = n - 1;Initialize horizontal boundaries

let direction = 0;Start moving right

while (left <= right && top <= bottom)Loop until boundaries cross

if (direction === 0)Fill top row left to right

top++;Shrink top boundary after filling

else if (direction === 1)Fill right column top to bottom

right--;Shrink right boundary after filling

else if (direction === 2)Fill bottom row right to left

bottom--;Shrink bottom boundary after filling

elseFill left column bottom to top

left++;Shrink left boundary after filling

direction = (direction + 1) % 4;Cycle direction clockwise

⏱

Complexity

TimeO(n^2)

SpaceO(n^2)

Each cell is filled exactly once, and direction changes are constant time operations.

💡 For n=10, this means 100 operations, which is efficient and straightforward.

Interview Verdict: Accepted

This approach is a good balance of clarity and efficiency, suitable for interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 Approach 1 is easiest to understand and implement, Approach 2 is cleaner with direction vectors, and Approach 3 balances clarity and efficiency. Approach 2 or 3 is recommended for interviews.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Boundary Checks)	O(n^2)	O(n^2)	No	N/A	Good for initial explanation and correctness
2. Directional Simulation with Vectors	O(n^2)	O(n^2)	No	N/A	Preferred for clean and maintainable code
3. Boundary Shrinking with Direction Index	O(n^2)	O(n^2)	No	N/A	Balanced approach, good for coding interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice multiple approaches, and prepare to explain your reasoning clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach simulating spiral filling with boundaries.Step 3: Explain how direction vectors can simplify the code.Step 4: Discuss boundary shrinking with direction indexing for clean implementation.Step 5: Code your chosen approach carefully, then test with edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Interviewers test your ability to manage multiple pointers, boundary conditions, and direction changes without errors, as well as your code clarity and testing rigor.

Common Follow-ups

• How would you modify the code to fill the matrix in counter-clockwise spiral order? → Change direction vectors or order.
• Can you generate the spiral matrix in-place if given a partially filled matrix? → Discuss in-place constraints and feasibility.

💡 These follow-ups test your flexibility with direction logic and understanding of in-place algorithms.

🔍

Pattern Recognition

When to Use

1) When asked to traverse or fill a matrix in a spiral order, 2) When boundaries shrink inward layer by layer, 3) When direction changes cyclically, 4) When output is a matrix or list in spiral order.

Signature Phrases

fill elements in spiral ordermove clockwise around the matrixshrink boundaries after each pass

NOT This Pattern When

Problems involving simple row/column traversal or diagonal traversal without boundary shrinking are different patterns.

Similar Problems

Spiral Matrix I - reading elements in spiral order instead of fillingRotate Image - rotating matrix layers which also involves boundary shrinkingMatrix Layer Rotation - rotating matrix layers similar to spiral traversal

Practice

1. Given the following Python code for diagonal traversal, what is the final output when the input matrix is [[1,2,3],[4,5,6],[7,8,9]]?

easy

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

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

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

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

Solution

1. Step 1: Trace diagonal 0 (d=0)

   r_start=0, r_end=0, even diagonal -> traverse from r_end down to r_start: mat[0][0]=1

2. Step 2: Trace diagonal 1 (d=1)

   r_start=0, r_end=1, odd diagonal -> traverse from r_start up to r_end: mat[0][1]=2, mat[1][0]=4

3. Step 3: Trace diagonal 2 (d=2)

   r_start=0, r_end=2, even diagonal -> traverse from r_end down to r_start: mat[2][0]=7, mat[1][1]=5, mat[0][2]=3

4. Step 4: Trace diagonal 3 (d=3)

   r_start=1, r_end=2, odd diagonal -> traverse from r_start up to r_end: mat[1][2]=6, mat[2][1]=8

5. Step 5: Trace diagonal 4 (d=4)

   r_start=2, r_end=2, even diagonal -> traverse from r_end down to r_start: mat[2][2]=9

6. Final Answer:

   Option A -> Option A

7. Quick Check:

   Output matches expected zigzag diagonal order [OK]

Hint: Even diagonals traverse down, odd diagonals traverse up [OK]

Common Mistakes:

• Mixing traversal direction for even/odd diagonals

2. You are given a 2D matrix and asked to output all elements starting from the outermost layer and moving inward in a clockwise manner, visiting each element exactly once. Which algorithmic approach best guarantees an efficient and correct solution for this problem?

easy

A. Perform a depth-first search (DFS) starting from the top-left corner, marking visited cells to avoid repeats.

B. Use a greedy approach that picks the next available element in clockwise order without tracking boundaries.

C. Apply dynamic programming to store intermediate traversal states and build the spiral order iteratively.

D. Simulate the traversal by shrinking the boundaries inward after completing each outer layer, ensuring no element is revisited.

Solution

1. Step 1: Understand the problem constraints

   The problem requires visiting all elements in a matrix in a spiral order without repetition, moving layer by layer inward.

2. Step 2: Identify the approach that guarantees correctness and efficiency

   Simulating the traversal by shrinking boundaries after completing each layer ensures no element is revisited and the traversal is orderly and complete.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Boundary shrinking matches the spiral traversal pattern perfectly [OK]

Hint: Boundary shrinking ensures no repeats and full coverage [OK]

Common Mistakes:

• Greedy approach misses boundary checks causing repeats
• DFS can revisit or miss elements without careful visited tracking
• DP is not suitable for traversal order problems

3. Consider this buggy version of the optimal Set Matrix Zeroes code. Which line contains the subtle bug that causes incorrect zeroing in some cases?

def setZeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    first_row_zero = any(matrix[0][j] == 0 for j in range(n))
    first_col_zero = any(matrix[i][0] == 0 for i in range(m))
    for i in range(m):  # Bug here: starts from 0 instead of 1
        for j in range(n):
            if matrix[i][j] == 0:
                matrix[i][0] = 0
                matrix[0][j] = 0
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0
    if first_row_zero:
        for j in range(n):
            matrix[0][j] = 0
    if first_col_zero:
        for i in range(m):
            matrix[i][0] = 0

medium

A. Line with 'for i in range(m):' (marking zeros in first pass)

B. Line with 'first_row_zero = any(matrix[0][j] == 0 for j in range(n))'

C. Line with 'first_col_zero = any(matrix[i][0] == 0 for i in range(m))'

D. Line with 'for i in range(1, m):' (zeroing based on flags)

Solution

1. Step 1: Identify marking loop range

   The marking loop should start from 1 to avoid overwriting first row/column flags prematurely.

2. Step 2: Understand impact

   Starting from 0 causes first row/column to be overwritten before flags are saved, losing zero info.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing loop to start at 1 fixes the bug [OK]

Hint: Mark zeros starting from index 1 to preserve flags [OK]

Common Mistakes:

• Zeroing first row/column too early
• Incorrect loop ranges causing info loss
• Confusing first pass marking with zeroing pass

4. 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

5. Suppose you want to extend diagonal traversal to handle matrices where elements can be updated dynamically and you need to output the diagonal traversal multiple times efficiently. Which modification to the algorithm is most appropriate?

hard

A. Precompute and store all diagonals in separate lists to allow O(1) retrieval per traversal.

B. Use the original traversal code each time since it is already optimal with O(m*n) time.

C. Flatten the matrix into a 1D array and sort it to simulate diagonal traversal.

D. Maintain a segment tree per diagonal to support dynamic updates and queries efficiently.

Solution

1. Step 1: Understand the requirement for dynamic updates

   Repeated diagonal traversals with updates require efficient update and query support.

2. Step 2: Evaluate options for dynamic support

   Precomputing diagonals (A) is fast for static data but inefficient for updates. Original code (B) recomputes fully each time. Flattening and sorting (D) loses diagonal order and is inefficient.

3. Step 3: Use segment trees per diagonal

   Segment trees allow efficient updates and queries on each diagonal, enabling fast repeated traversals.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Segment trees balance update and query efficiency for dynamic diagonal traversal [OK]

Hint: Dynamic updates require data structures supporting fast queries [OK]

Common Mistakes:

• Assuming original code is always optimal for dynamic queries