Spiral Matrix

54.Spiral Matrix

Array

Matrix

Simulation

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.

Example:

Input:

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

→

Output:

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

Elements are returned in spiral order: right → down → left → up

Algorithm:

1. Define four boundaries: rowStart, rowEnd, colStart, colEnd
2. While boundaries don't cross, traverse in four directions:
3. Right: traverse current top row (rowStart)
4. Down: traverse current rightmost column (colEnd)
5. Left: traverse current bottom row (rowEnd)
6. Up: traverse current leftmost column (colStart)
7. After each traversal, update boundaries accordingly

Complexity:

Time: O(m×n) | Space: O(1)

Excluding the space needed for output array

Java Solution:

public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> res = new ArrayList<>();
    
    if (matrix.length == 0) return res;
    
    int rowStart = 0, rowEnd = matrix.length - 1;
    int colStart = 0, colEnd = matrix[0].length - 1;
    
    while (rowStart <= rowEnd && colStart <= colEnd) {
        // Traverse Right
        for (int j = colStart; j <= colEnd; j++) 
            res.add(matrix[rowStart][j]);
        rowStart++;    // Move down after traversing top row
        
        // Traverse Down
        for (int i = rowStart; i <= rowEnd; i++) 
            res.add(matrix[i][colEnd]);
        colEnd--;      // Move left after traversing right column
        
        // Check before traversing left
        if (rowStart <= rowEnd) {
            // Traverse Left
            for (int j = colEnd; j >= colStart; j--) 
                res.add(matrix[rowEnd][j]);
            rowEnd--;  // Move up after traversing bottom row
        }
        
        // Check before traversing up
        if (colStart <= colEnd) {
            // Traverse Up
            for (int i = rowEnd; i >= rowStart; i--) 
                res.add(matrix[i][colStart]);
            colStart++; // Move right after traversing left column
        }
    }
    
    return res;
}

Python Solution:

def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
    if not matrix: return []
    
    result = []
    row_start, row_end = 0, len(matrix) - 1
    col_start, col_end = 0, len(matrix[0]) - 1
    
    while row_start <= row_end and col_start <= col_end:
        # Traverse Right
        result.extend(matrix[row_start][j] for j in range(col_start, col_end + 1))
        row_start += 1
        
        # Traverse Down
        result.extend(matrix[i][col_end] for i in range(row_start, row_end + 1))
        col_end -= 1
        
        if row_start <= row_end:
            # Traverse Left
            result.extend(matrix[row_end][j] for j in range(col_end, col_start - 1, -1))
            row_end -= 1
        
        if col_start <= col_end:
            # Traverse Up
            result.extend(matrix[i][col_start] for i in range(row_end, row_start - 1, -1))
            col_start += 1
    
    return result

C++ Solution:

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    vector<int> result;
    if (matrix.empty()) return result;
    
    int row_start = 0, row_end = matrix.size() - 1;
    int col_start = 0, col_end = matrix[0].size() - 1;
    
    while (row_start <= row_end && col_start <= col_end) {
        // Traverse Right
        for (int j = col_start; j <= col_end; j++)
            result.push_back(matrix[row_start][j]);
        row_start++;
        
        // Traverse Down
        for (int i = row_start; i <= row_end; i++)
            result.push_back(matrix[i][col_end]);
        col_end--;
        
        if (row_start <= row_end) {
            // Traverse Left
            for (int j = col_end; j >= col_start; j--)
                result.push_back(matrix[row_end][j]);
            row_end--;
        }
        
        if (col_start <= col_end) {
            // Traverse Up
            for (int i = row_end; i >= row_start; i--)
                result.push_back(matrix[i][col_start]);
            col_start++;
        }
    }
    
    return result;
}