Spiral Matrix Traversal

Problem

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

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

Python Solution

def spiral_order(matrix):
    result = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    while top <= bottom and left <= right:
        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

C++ Solution

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    vector<int> result;
    int top = 0, bottom = matrix.size() - 1;
    int left = 0, right = matrix[0].size() - 1;
    while (top <= bottom && left <= right) {
        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;
}

Java Solution

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

Complexity

Time: O(m × n) — every cell of the matrix is visited exactly once as the boundary shrinks inward. Space: O(1) extra, not counting the output list, since only four boundary pointers are tracked.