Spiral Matrix (Read Outward Spiral)

🎯

Spiral Matrix (Read Outward Spiral)

mediumMATRIXAmazonMicrosoftGoogle

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.

💡 This problem is about traversing a 2D matrix in a spiral order. Beginners often struggle because it requires careful boundary management and multiple direction changes, which can be confusing without a systematic approach.

📋

Problem Statement

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

💡

Example

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

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

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.

• Single row matrix → output is the row itself
• Single column matrix → output is the column itself
• Matrix with one element → output is that element
• Rectangular matrix (m != n) → spiral still works correctly

⚠️

Common Mistakes

Not updating boundaries correctly after each traversal

Infinite loop or repeated elements in output

✅ Ensure boundaries are incremented/decremented after each edge traversal

Not checking boundary conditions before traversing bottom row or left column

Duplicate elements or index out of range errors

✅ Add checks like if (top <= bottom) and if (left <= right) before those traversals

Using visited matrix but forgetting to mark cells visited

Infinite loops or repeated elements

✅ Mark each visited cell immediately after adding to result

Incorrect direction changes in simulation approach

Wrong traversal order or index errors

✅ Change direction only when next cell is invalid or visited, and update position accordingly

Not handling single row or single column matrices separately

Index errors or missing elements

✅ Boundary checks naturally handle these, but test explicitly

🧠

Brute Force (Nested Loops with Boundary Checks)

💡 Starting with a brute force approach helps understand the problem deeply by manually simulating the spiral traversal using explicit loops and boundary variables.

Intuition

We keep track of four boundaries (top, bottom, left, right) and iterate over the matrix edges in a clockwise manner, shrinking the boundaries after each edge traversal until all elements are visited.

Algorithm

1. Initialize four pointers: top, bottom, left, right to represent current boundaries.
2. Traverse from left to right along the top boundary, then increment top.
3. Traverse from top to bottom along the right boundary, then decrement right.
4. Traverse from right to left along the bottom boundary, then decrement bottom.
5. Traverse from bottom to top along the left boundary, then increment left.
6. Repeat steps 2-5 until all elements are traversed.

💡 The challenge is to carefully update boundaries and check conditions to avoid revisiting elements or going out of bounds.

</>

Code

from typing import List

def spiralOrder(matrix: List[List[int]]) -> List[int]:
    if not matrix or not matrix[0]:
        return []
    result = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    while left <= right and top <= bottom:
        for col in range(left, right + 1):
            result.append(matrix[top][col])
        top += 1
        for row in range(top, bottom + 1):
            result.append(matrix[row][right])
        right -= 1
        if top <= bottom:
            for col in range(right, left - 1, -1):
                result.append(matrix[bottom][col])
            bottom -= 1
        if left <= right:
            for row in range(bottom, top - 1, -1):
                result.append(matrix[row][left])
            left += 1
    return result

# Driver code
if __name__ == '__main__':
    mat = [[1,2,3],[4,5,6],[7,8,9]]
    print(spiralOrder(mat))  # Expected: [1,2,3,6,9,8,7,4,5]

Line Notes

if not matrix or not matrix[0]:Check for empty matrix to avoid errors

top, bottom = 0, len(matrix) - 1Initialize vertical boundaries

left, right = 0, len(matrix[0]) - 1Initialize horizontal boundaries

while left <= right and top <= bottom:Loop until boundaries cross, meaning all elements are visited

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

top += 1Shrink top boundary after traversal

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

right -= 1Shrink right boundary after traversal

if top <= bottom:Check to avoid double counting rows

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

bottom -= 1Shrink bottom boundary after traversal

if left <= right:Check to avoid double counting columns

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

left += 1Shrink left boundary after traversal

import java.util.*;

public class SpiralMatrix {
    public static List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        if (matrix == null || matrix.length == 0) return result;
        int top = 0, bottom = matrix.length - 1;
        int left = 0, right = matrix[0].length - 1;
        while (left <= right && top <= bottom) {
            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;
    }

    public static void main(String[] args) {
        int[][] mat = {{1,2,3},{4,5,6},{7,8,9}};
        System.out.println(spiralOrder(mat)); // Expected: [1, 2, 3, 6, 9, 8, 7, 4, 5]
    }
}

Line Notes

if (matrix == null || matrix.length == 0)Check for empty input to avoid exceptions

int top = 0, bottom = matrix.length - 1;Initialize vertical boundaries

int left = 0, right = matrix[0].length - 1;Initialize horizontal boundaries

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

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

top++;Move top boundary down

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

right--;Move right boundary left

if (top <= bottom)Check to avoid double counting bottom row

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

bottom--;Move bottom boundary up

if (left <= right)Check to avoid double counting left column

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

left++;Move left boundary right

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

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    vector<int> result;
    if (matrix.empty() || matrix[0].empty()) return result;
    int top = 0, bottom = matrix.size() - 1;
    int left = 0, right = matrix[0].size() - 1;
    while (left <= right && top <= bottom) {
        for (int col = left; col <= right; ++col) {
            result.push_back(matrix[top][col]);
        }
        top++;
        for (int row = top; row <= bottom; ++row) {
            result.push_back(matrix[row][right]);
        }
        right--;
        if (top <= bottom) {
            for (int col = right; col >= left; --col) {
                result.push_back(matrix[bottom][col]);
            }
            bottom--;
        }
        if (left <= right) {
            for (int row = bottom; row >= top; --row) {
                result.push_back(matrix[row][left]);
            }
            left++;
        }
    }
    return result;
}

int main() {
    vector<vector<int>> mat = {{1,2,3},{4,5,6},{7,8,9}};
    vector<int> res = spiralOrder(mat);
    for (int num : res) cout << num << " ";
    cout << endl; // Expected: 1 2 3 6 9 8 7 4 5
    return 0;
}

Line Notes

if (matrix.empty() || matrix[0].empty()) return result;Guard clause for empty matrix

int top = 0, bottom = matrix.size() - 1;Set vertical boundaries

int left = 0, right = matrix[0].size() - 1;Set horizontal boundaries

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

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

top++;Shrink top boundary

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

right--;Shrink right boundary

if (top <= bottom)Check to avoid revisiting bottom row

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

bottom--;Shrink bottom boundary

if (left <= right)Check to avoid revisiting left column

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

left++;Shrink left boundary

function spiralOrder(matrix) {
    if (!matrix.length || !matrix[0].length) return [];
    const result = [];
    let top = 0, bottom = matrix.length - 1;
    let left = 0, right = matrix[0].length - 1;
    while (left <= right && top <= bottom) {
        for (let col = left; col <= right; col++) {
            result.push(matrix[top][col]);
        }
        top++;
        for (let row = top; row <= bottom; row++) {
            result.push(matrix[row][right]);
        }
        right--;
        if (top <= bottom) {
            for (let col = right; col >= left; col--) {
                result.push(matrix[bottom][col]);
            }
            bottom--;
        }
        if (left <= right) {
            for (let row = bottom; row >= top; row--) {
                result.push(matrix[row][left]);
            }
            left++;
        }
    }
    return result;
}

// Test
const mat = [[1,2,3],[4,5,6],[7,8,9]];
console.log(spiralOrder(mat)); // Expected: [1,2,3,6,9,8,7,4,5]

Line Notes

if (!matrix.length || !matrix[0].length) return [];Check for empty matrix input

let top = 0, bottom = matrix.length - 1;Initialize vertical boundaries

let left = 0, right = matrix[0].length - 1;Initialize horizontal boundaries

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

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

top++;Move top boundary down

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

right--;Move right boundary left

if (top <= bottom)Check to avoid double counting bottom row

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

bottom--;Move bottom boundary up

if (left <= right)Check to avoid double counting left column

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

left++;Move left boundary right

⏱

Complexity

TimeO(m*n)

SpaceO(m*n)

We visit each element exactly once, so time complexity is proportional to the number of elements. The output list stores all elements, so space complexity is also proportional to the number of elements.

💡 For a 10x10 matrix, this means 100 operations, which is efficient and practical.

Interview Verdict: Accepted

This approach is efficient and accepted for typical interview constraints, making it a solid baseline solution.

🧠

Simulation with Direction Vectors

💡 This approach uses direction vectors and a visited matrix to simulate the spiral traversal, which helps beginners understand direction changes and boundary conditions more explicitly.

Intuition

We move in one direction until we hit a boundary or visited cell, then turn right (change direction) and continue until all cells are visited.

Algorithm

1. Initialize direction vectors for right, down, left, and up movements.
2. Create a visited matrix to mark visited cells.
3. Start from (0,0) and move in the current direction.
4. If next cell is out of bounds or visited, turn right (change direction).
5. Continue until all cells are visited.

💡 This approach explicitly models movement and direction changes, which can be easier to visualize but requires extra space for visited tracking.

</>

Code

from typing import List

def spiralOrder(matrix: List[List[int]]) -> List[int]:
    if not matrix or not matrix[0]:
        return []
    m, n = len(matrix), len(matrix[0])
    visited = [[False]*n for _ in range(m)]
    result = []
    directions = [(0,1),(1,0),(0,-1),(-1,0)]  # right, down, left, up
    dir_idx = 0
    r = c = 0
    for _ in range(m*n):
        result.append(matrix[r][c])
        visited[r][c] = True
        dr, dc = directions[dir_idx]
        nr, nc = r + dr, c + dc
        if nr < 0 or nr >= m or nc < 0 or nc >= n or visited[nr][nc]:
            dir_idx = (dir_idx + 1) % 4
            dr, dc = directions[dir_idx]
            nr, nc = r + dr, c + dc
        r, c = nr, nc
    return result

# Driver code
if __name__ == '__main__':
    mat = [[1,2,3],[4,5,6],[7,8,9]]
    print(spiralOrder(mat))  # Expected: [1,2,3,6,9,8,7,4,5]

Line Notes

visited = [[False]*n for _ in range(m)]Track which cells have been visited to avoid repeats

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

dir_idx = 0Start moving right

for _ in range(m*n):Visit all cells exactly once

if nr < 0 or nr >= m or nc < 0 or nc >= n or visited[nr][nc]:Check if next cell is invalid or visited

dir_idx = (dir_idx + 1) % 4Turn right by cycling direction index

r, c = nr, ncMove to next valid cell

import java.util.*;

public class SpiralMatrix {
    public static List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        if (matrix == null || matrix.length == 0) return result;
        int m = matrix.length, n = matrix[0].length;
        boolean[][] visited = new boolean[m][n];
        int[][] directions = {{0,1},{1,0},{0,-1},{-1,0}};
        int dirIdx = 0, r = 0, c = 0;
        for (int i = 0; i < m * n; i++) {
            result.add(matrix[r][c]);
            visited[r][c] = true;
            int nr = r + directions[dirIdx][0];
            int nc = c + directions[dirIdx][1];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n || visited[nr][nc]) {
                dirIdx = (dirIdx + 1) % 4;
                nr = r + directions[dirIdx][0];
                nc = c + directions[dirIdx][1];
            }
            r = nr;
            c = nc;
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] mat = {{1,2,3},{4,5,6},{7,8,9}};
        System.out.println(spiralOrder(mat)); // Expected: [1, 2, 3, 6, 9, 8, 7, 4, 5]
    }
}

Line Notes

boolean[][] visited = new boolean[m][n];Track visited cells to prevent repeats

int[][] directions = {{0,1},{1,0},{0,-1},{-1,0}};Movement vectors for directions

int dirIdx = 0, r = 0, c = 0;Start at top-left moving right

for (int i = 0; i < m * n; i++)Visit all cells once

if (nr < 0 || nr >= m || nc < 0 || nc >= n || visited[nr][nc])Check boundary and visited conditions

dirIdx = (dirIdx + 1) % 4;Turn right when blocked

r = nr; c = nc;Move to next cell

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

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    vector<int> result;
    if (matrix.empty() || matrix[0].empty()) return result;
    int m = matrix.size(), n = matrix[0].size();
    vector<vector<bool>> visited(m, vector<bool>(n, false));
    vector<pair<int,int>> directions = {{0,1},{1,0},{0,-1},{-1,0}};
    int dirIdx = 0, r = 0, c = 0;
    for (int i = 0; i < m * n; ++i) {
        result.push_back(matrix[r][c]);
        visited[r][c] = true;
        int nr = r + directions[dirIdx].first;
        int nc = c + directions[dirIdx].second;
        if (nr < 0 || nr >= m || nc < 0 || nc >= n || visited[nr][nc]) {
            dirIdx = (dirIdx + 1) % 4;
            nr = r + directions[dirIdx].first;
            nc = c + directions[dirIdx].second;
        }
        r = nr;
        c = nc;
    }
    return result;
}

int main() {
    vector<vector<int>> mat = {{1,2,3},{4,5,6},{7,8,9}};
    vector<int> res = spiralOrder(mat);
    for (int num : res) cout << num << " ";
    cout << endl; // Expected: 1 2 3 6 9 8 7 4 5
    return 0;
}

Line Notes

vector<vector<bool>> visited(m, vector<bool>(n, false));Keep track of visited cells

vector<pair<int,int>> directions = {{0,1},{1,0},{0,-1},{-1,0}};Direction vectors for movement

int dirIdx = 0, r = 0, c = 0;Start position and direction

for (int i = 0; i < m * n; ++i)Loop to visit all cells

if (nr < 0 || nr >= m || nc < 0 || nc >= n || visited[nr][nc])Check if next cell is invalid or visited

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

r = nr; c = nc;Update current position

function spiralOrder(matrix) {
    if (!matrix.length || !matrix[0].length) return [];
    const m = matrix.length, n = matrix[0].length;
    const visited = Array.from({length: m}, () => Array(n).fill(false));
    const directions = [[0,1],[1,0],[0,-1],[-1,0]];
    let dirIdx = 0, r = 0, c = 0;
    const result = [];
    for (let i = 0; i < m * n; i++) {
        result.push(matrix[r][c]);
        visited[r][c] = true;
        let nr = r + directions[dirIdx][0];
        let nc = c + directions[dirIdx][1];
        if (nr < 0 || nr >= m || nc < 0 || nc >= n || visited[nr][nc]) {
            dirIdx = (dirIdx + 1) % 4;
            nr = r + directions[dirIdx][0];
            nc = c + directions[dirIdx][1];
        }
        r = nr;
        c = nc;
    }
    return result;
}

// Test
const mat = [[1,2,3],[4,5,6],[7,8,9]];
console.log(spiralOrder(mat)); // Expected: [1,2,3,6,9,8,7,4,5]

Line Notes

const visited = Array.from({length: m}, () => Array(n).fill(false));Create visited matrix to track cells

const directions = [[0,1],[1,0],[0,-1],[-1,0]];Define movement directions

let dirIdx = 0, r = 0, c = 0;Initialize starting position and direction

for (let i = 0; i < m * n; i++)Loop to visit all elements

if (nr < 0 || nr >= m || nc < 0 || nc >= n || visited[nr][nc])Check if next move is invalid or visited

dirIdx = (dirIdx + 1) % 4;Turn right when blocked

r = nr; c = nc;Update current position

⏱

Complexity

TimeO(m*n)

SpaceO(m*n)

We visit each element once, but use extra space for the visited matrix, increasing space complexity.

💡 For a 10x10 matrix, this means 100 operations plus 100 boolean flags stored.

Interview Verdict: Accepted

This approach is intuitive and accepted but uses extra space, which might be suboptimal for large inputs.

🧠

In-place Boundary Shrinking Without Extra Space

💡 This approach optimizes space by avoiding a visited matrix and relies solely on boundary pointers to control traversal, making it efficient and clean.

Intuition

By shrinking the boundaries inward after traversing each edge, we ensure no element is visited twice without needing extra memory.

Algorithm

1. Initialize top, bottom, left, right boundaries.
2. Traverse top row from left to right, then increment top.
3. Traverse right column from top to bottom, then decrement right.
4. Traverse bottom row from right to left if top <= bottom, then decrement bottom.
5. Traverse left column from bottom to top if left <= right, then increment left.
6. Repeat until boundaries cross.

💡 This approach is similar to brute force but emphasizes no extra space and careful boundary checks.

</>

Code

from typing import List

def spiralOrder(matrix: List[List[int]]) -> List[int]:
    if not matrix or not matrix[0]:
        return []
    result = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    while left <= right and top <= bottom:
        result.extend(matrix[top][left:right+1])
        top += 1
        for row in range(top, bottom + 1):
            result.append(matrix[row][right])
        right -= 1
        if top <= bottom:
            for col in range(right, left - 1, -1):
                result.append(matrix[bottom][col])
            bottom -= 1
        if left <= right:
            for row in range(bottom, top - 1, -1):
                result.append(matrix[row][left])
            left += 1
    return result

# Driver code
if __name__ == '__main__':
    mat = [[1,2,3],[4,5,6],[7,8,9]]
    print(spiralOrder(mat))  # Expected: [1,2,3,6,9,8,7,4,5]

Line Notes

result.extend(matrix[top][left:right+1])Add entire top row slice at once for efficiency

top += 1Move top boundary down after traversal

for row in range(top, bottom + 1):Traverse right column downwards

right -= 1Move right boundary left

if top <= bottom:Check to avoid double counting bottom row

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

bottom -= 1Move bottom boundary up

if left <= right:Check to avoid double counting left column

for row in range(bottom, top - 1, -1):Traverse left column upwards

left += 1Move left boundary right

import java.util.*;

public class SpiralMatrix {
    public static List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        if (matrix == null || matrix.length == 0) return result;
        int top = 0, bottom = matrix.length - 1;
        int left = 0, right = matrix[0].length - 1;
        while (left <= right && top <= bottom) {
            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;
    }

    public static void main(String[] args) {
        int[][] mat = {{1,2,3},{4,5,6},{7,8,9}};
        System.out.println(spiralOrder(mat)); // Expected: [1, 2, 3, 6, 9, 8, 7, 4, 5]
    }
}

Line Notes

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

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

top++;Shrink top boundary

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

right--;Shrink right boundary

if (top <= bottom)Check to avoid double counting bottom row

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

bottom--;Shrink bottom boundary

if (left <= right)Check to avoid double counting left column

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

left++;Shrink left boundary

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

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    vector<int> result;
    if (matrix.empty() || matrix[0].empty()) return result;
    int top = 0, bottom = matrix.size() - 1;
    int left = 0, right = matrix[0].size() - 1;
    while (left <= right && top <= bottom) {
        for (int col = left; col <= right; ++col) {
            result.push_back(matrix[top][col]);
        }
        top++;
        for (int row = top; row <= bottom; ++row) {
            result.push_back(matrix[row][right]);
        }
        right--;
        if (top <= bottom) {
            for (int col = right; col >= left; --col) {
                result.push_back(matrix[bottom][col]);
            }
            bottom--;
        }
        if (left <= right) {
            for (int row = bottom; row >= top; --row) {
                result.push_back(matrix[row][left]);
            }
            left++;
        }
    }
    return result;
}

int main() {
    vector<vector<int>> mat = {{1,2,3},{4,5,6},{7,8,9}};
    vector<int> res = spiralOrder(mat);
    for (int num : res) cout << num << " ";
    cout << endl; // Expected: 1 2 3 6 9 8 7 4 5
    return 0;
}

Line Notes

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

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

top++;Shrink top boundary

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

right--;Shrink right boundary

if (top <= bottom)Check to avoid revisiting bottom row

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

bottom--;Shrink bottom boundary

if (left <= right)Check to avoid revisiting left column

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

left++;Shrink left boundary

function spiralOrder(matrix) {
    if (!matrix.length || !matrix[0].length) return [];
    const result = [];
    let top = 0, bottom = matrix.length - 1;
    let left = 0, right = matrix[0].length - 1;
    while (left <= right && top <= bottom) {
        for (let col = left; col <= right; col++) {
            result.push(matrix[top][col]);
        }
        top++;
        for (let row = top; row <= bottom; row++) {
            result.push(matrix[row][right]);
        }
        right--;
        if (top <= bottom) {
            for (let col = right; col >= left; col--) {
                result.push(matrix[bottom][col]);
            }
            bottom--;
        }
        if (left <= right) {
            for (let row = bottom; row >= top; row--) {
                result.push(matrix[row][left]);
            }
            left++;
        }
    }
    return result;
}

// Test
const mat = [[1,2,3],[4,5,6],[7,8,9]];
console.log(spiralOrder(mat)); // Expected: [1,2,3,6,9,8,7,4,5]

Line Notes

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

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

top++;Shrink top boundary

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

right--;Shrink right boundary

if (top <= bottom)Check to avoid double counting bottom row

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

bottom--;Shrink bottom boundary

if (left <= right)Check to avoid double counting left column

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

left++;Shrink left boundary

⏱

Complexity

TimeO(m*n)

SpaceO(m*n)

Each element is visited once, and no extra space besides output list is used, making it optimal in space.

💡 For a 10x10 matrix, this means 100 operations and minimal extra memory usage.

Interview Verdict: Accepted

This is the preferred approach in interviews due to its clarity and optimal space usage.

📊

All Approaches - One-Glance Tradeoffs

💡 The boundary shrinking approach is the best to code in interviews due to its clarity and optimal space usage.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Boundary Pointers)	O(m*n)	O(m*n) output only	No	N/A	Good to explain first, then optimize
2. Simulation with Direction Vectors	O(m*n)	O(m*n) output + O(m*n) visited	No	N/A	Explain as alternative, less optimal due to extra space
3. In-place Boundary Shrinking	O(m*n)	O(m*n) output only	No	N/A	Preferred approach to implement

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly during interviews.

How to Present

Clarify input size and matrix shapeState the brute force approach with boundary pointersExplain simulation with direction vectors as an alternativePresent the optimal boundary shrinking approachCode the optimal approach and test edge cases

Time Allocation

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

What the Interviewer Tests

Ability to manage boundaries correctly, handle edge cases, and write clean, bug-free code with clear explanations.

Common Follow-ups

• How to handle non-rectangular matrices → Usually invalid input or pad with defaults
• Can you do this in-place modifying the input matrix? → Not generally, as output order differs

💡 Follow-ups test your understanding of input constraints and ability to adapt the solution.

🔍

Pattern Recognition

When to Use

1) Asked to traverse matrix in spiral or circular layers; 2) Need to visit all elements exactly once; 3) Boundaries shrink inward; 4) Direction changes in fixed order

Signature Phrases

spiral orderclockwise traversalboundary shrinkinglayer by layer

NOT This Pattern When

Snake pattern traversal or diagonal traversal problems, which have different movement logic

Similar Problems

Rotate Image - involves rotating matrix layers similarlyMatrix Layer Rotation - rotate each layer in spiral orderZigzag Matrix Traversal - different pattern but also matrix 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. What is the time complexity of the optimal approach that precomputes row minimums and column maximums and then finds lucky numbers in a matrix of size m x n?

medium

A. O(m * n * (m + n)) because each element is checked against entire row and column.

B. O(m + n) because only minimums and maximums arrays are computed without scanning the entire matrix.

C. O(m * n * log(m + n)) due to sorting rows and columns before checking.

D. O(m * n) because row minimums and column maximums are computed in separate passes and then a single pass finds lucky numbers.

Solution

1. Step 1: Identify complexity of computing row minimums

   Computing min for each of m rows requires O(m * n) time.

2. Step 2: Identify complexity of computing column maximums

   Computing max for each of n columns requires O(m * n) time.

3. Step 3: Single pass to find lucky numbers

   Iterating over all m*n elements to check conditions is O(m * n).

4. Step 4: Combine all steps

   Total time is O(m * n) + O(m * n) + O(m * n) = O(m * n).

5. Final Answer:

   Option D -> Option D

6. Quick Check:

   Precompute and single pass -> linear in matrix size [OK]

Hint: Precompute arrays then single pass -> O(m*n) [OK]

Common Mistakes:

• Confusing brute force complexity with optimal
• Ignoring single pass after precomputation
• Assuming sorting is needed

3. Consider the following buggy code for maximum hourglass sum using sliding window. Which line contains the subtle bug that can cause incorrect results when all matrix values are negative?

def max_hourglass_sum_sliding(matrix):
    n = len(matrix)
    m = len(matrix[0])
    max_sum = 0  # Bug here

    for i in range(n - 2):
        current_sum = (matrix[i][0] + matrix[i][1] + matrix[i][2] +
                       matrix[i+1][1] +
                       matrix[i+2][0] + matrix[i+2][1] + matrix[i+2][2])
        if current_sum > max_sum:
            max_sum = current_sum

        for j in range(1, m - 2):
            current_sum -= (matrix[i][j-1] + matrix[i+1][j] + matrix[i+2][j-1])
            current_sum += (matrix[i][j+2] + matrix[i+1][j+1] + matrix[i+2][j+2])
            if current_sum > max_sum:
                max_sum = current_sum
    return max_sum

medium

A. Line initializing max_sum to 0

B. Line computing current_sum for initial hourglass

C. Line subtracting left column elements in sliding window

D. Line adding right column elements in sliding window

Solution

1. Step 1: Understand initialization of max_sum

   Setting max_sum = 0 causes incorrect max when all values are negative, as max_sum never updates to negative sums.

2. Step 2: Confirm other lines are correct

   Current_sum calculation and sliding window updates are correct; bug is only in initialization.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Proper initialization must be -inf to handle negative values [OK]

Hint: Initialize max_sum to -inf to handle negative values [OK]

Common Mistakes:

• Initializing max_sum to 0
• Misindexing sliding window updates
• Forgetting to update max_sum after sliding

4. Consider the following buggy code snippet for generating an n x n spiral matrix. Which line contains the subtle bug that can cause incorrect output or infinite loops?

medium

A. Line updating 'right' boundary after downward fill

B. Line after filling top row: missing update of 'top' boundary

C. Line updating 'bottom' boundary after leftward fill

D. Line updating 'left' boundary after upward fill

Solution

1. Step 1: Identify boundary updates after each direction

   After filling the top row (direction 0), the 'top' boundary must be incremented to avoid overwriting.

2. Step 2: Locate missing update

   The code comment indicates the 'top' boundary update is missing, causing the loop to overwrite the same row repeatedly or cause infinite loops.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing 'top += 1' causes repeated writes to top row [OK]

Hint: Each direction must update its boundary after filling [OK]

Common Mistakes:

• Forgetting to update one boundary after a direction
• Incorrectly updating boundaries leading to index errors
• Misordering direction cycling

5. Suppose the Sudoku validation problem is extended so that the board size is variable (N x N), where N is a perfect square (e.g., 4x4, 16x16), and digits range from 1 to N. Which of the following modifications to the bitmasking approach is necessary to correctly validate such boards?

hard

A. Use larger integer types or multiple integers to represent bitmasks since N can exceed 32 bits.

B. Keep the same 9x9 fixed-size arrays and bitmasks since the logic is identical regardless of N.

C. Replace bitmasking with hash sets because bitmasking only works for 9x9 boards.

D. Only check rows and columns; boxes are not needed for variable-sized boards.

Solution

1. Step 1: Understand bitmask size limitation

   Bitmasking uses bits to represent digits; for N > 32, a single integer is insufficient.

2. Step 2: Modify data structures accordingly

   Use larger integer types (e.g., 64-bit) or multiple integers/arrays to represent bitmasks for larger N.

3. Step 3: Confirm boxes must still be checked

   Boxes remain part of the constraints; logic must adapt to variable box sizes.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Bitmask size must scale with N to represent all digits [OK]

Hint: Bitmask size must scale with board size N [OK]

Common Mistakes:

• Assuming fixed 9x9 arrays suffice
• Dropping box checks
• Thinking bitmasking can't scale at all