54. Spiral Matrix

Medium

Problem Description

Given an m x n matrix, return all elements of the matrix in spiral order.

Examples

Example 1:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

Example 2:
Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]
Jump to Solution: Python Java C++ JavaScript C#

Python Solution


def spiralOrder(matrix: List[List[int]]) -> List[int]:
    result = []
    if not matrix:
        return result
    
    top, bottom = 0, len(matrix)
    left, right = 0, len(matrix[0])
    
    while left < right and top < bottom:
        # Traverse right
        for i in range(left, right):
            result.append(matrix[top][i])
        top += 1
        
        # Traverse down
        for i in range(top, bottom):
            result.append(matrix[i][right-1])
        right -= 1
        
        if not (left < right and top < bottom):
            break
            
        # Traverse left
        for i in range(right-1, left-1, -1):
            result.append(matrix[bottom-1][i])
        bottom -= 1
        
        # Traverse up
        for i in range(bottom-1, top-1, -1):
            result.append(matrix[i][left])
        left += 1
    
    return result

Java Solution


class Solution {
    public List spiralOrder(int[][] matrix) {
        List result = new ArrayList<>();
        if (matrix == null || matrix.length == 0) {
            return result;
        }
        
        int top = 0, bottom = matrix.length;
        int left = 0, right = matrix[0].length;
        
        while (left < right && top < bottom) {
            // Traverse right
            for (int i = left; i < right; i++) {
                result.add(matrix[top][i]);
            }
            top++;
            
            // Traverse down
            for (int i = top; i < bottom; i++) {
                result.add(matrix[i][right-1]);
            }
            right--;
            
            if (!(left < right && top < bottom)) {
                break;
            }
            
            // Traverse left
            for (int i = right-1; i >= left; i--) {
                result.add(matrix[bottom-1][i]);
            }
            bottom--;
            
            // Traverse up
            for (int i = bottom-1; i >= top; i--) {
                result.add(matrix[i][left]);
            }
            left++;
        }
        
        return result;
    }
}

C++ Solution


class Solution {
public:
    vector spiralOrder(vector>& matrix) {
        vector result;
        if (matrix.empty()) {
            return result;
        }
        
        int top = 0, bottom = matrix.size();
        int left = 0, right = matrix[0].size();
        
        while (left < right && top < bottom) {
            // Traverse right
            for (int i = left; i < right; i++) {
                result.push_back(matrix[top][i]);
            }
            top++;
            
            // Traverse down
            for (int i = top; i < bottom; i++) {
                result.push_back(matrix[i][right-1]);
            }
            right--;
            
            if (!(left < right && top < bottom)) {
                break;
            }
            
            // Traverse left
            for (int i = right-1; i >= left; i--) {
                result.push_back(matrix[bottom-1][i]);
            }
            bottom--;
            
            // Traverse up
            for (int i = bottom-1; i >= top; i--) {
                result.push_back(matrix[i][left]);
            }
            left++;
        }
        
        return result;
    }
};

JavaScript Solution


/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function(matrix) {
    const result = [];
    if (!matrix.length) {
        return result;
    }
    
    let top = 0, bottom = matrix.length;
    let left = 0, right = matrix[0].length;
    
    while (left < right && top < bottom) {
        // Traverse right
        for (let i = left; i < right; i++) {
            result.push(matrix[top][i]);
        }
        top++;
        
        // Traverse down
        for (let i = top; i < bottom; i++) {
            result.push(matrix[i][right-1]);
        }
        right--;
        
        if (!(left < right && top < bottom)) {
            break;
        }
        
        // Traverse left
        for (let i = right-1; i >= left; i--) {
            result.push(matrix[bottom-1][i]);
        }
        bottom--;
        
        // Traverse up
        for (let i = bottom-1; i >= top; i--) {
            result.push(matrix[i][left]);
        }
        left++;
    }
    
    return result;
};

C# Solution


public class Solution {
    public IList SpiralOrder(int[][] matrix) {
        IList result = new List();
        if (matrix == null || matrix.Length == 0) {
            return result;
        }
        
        int top = 0, bottom = matrix.Length;
        int left = 0, right = matrix[0].Length;
        
        while (left < right && top < bottom) {
            // Traverse right
            for (int i = left; i < right; i++) {
                result.Add(matrix[top][i]);
            }
            top++;
            
            // Traverse down
            for (int i = top; i < bottom; i++) {
                result.Add(matrix[i][right-1]);
            }
            right--;
            
            if (!(left < right && top < bottom)) {
                break;
            }
            
            // Traverse left
            for (int i = right-1; i >= left; i--) {
                result.Add(matrix[bottom-1][i]);
            }
            bottom--;
            
            // Traverse up
            for (int i = bottom-1; i >= top; i--) {
                result.Add(matrix[i][left]);
            }
            left++;
        }
        
        return result;
    }
}

Complexity Analysis

Solution Explanation

This solution uses a layer-by-layer approach to traverse the matrix in spiral order:

Key points: