54. Spiral Matrix

Intuition

The problem requires us to traverse a 2D matrix in a spiral order and return the elements in that order. Spiral order traversal means moving in a specific sequence: starting from the top-left corner, we move right across the top row, then down the rightmost column, then left across the bottom row, and then up the leftmost column. This process repeats for the inner layers of the matrix until all elements have been visited.

Approach

1. Initialization: - Determine the number of rows (m) and columns (n) in the matrix. - Initialize the result list res to store the elements in spiral order. - Initialize pointers for the current position (x, y) and direction (dx, dy). We start moving right, so dx = 1 and dy = 0.
2. Traverse the Matrix: - Loop through each cell in the matrix, based on the total number of elements (m * n). - For each cell: - Append the current cell's value to the result list res. - Mark the current cell as visited (e.g., by setting it to a special value like float('inf') which is out of the valid range for matrix elements).
3. Change Direction: - Check if the next cell (based on the current direction) is within bounds and not visited. - If the next cell is out of bounds or already visited, change the direction by rotating it clockwise. This is done by swapping dx and dy, and negating dy.
4. Move to the Next Cell: - Update the current position (x, y) based on the direction (dx, dy).
5. Return the Result: - Once all cells are visited, return the result list res containing the elements in spiral order.

Complexity

Time Complexity:

O(m * n)

• We visit each element in the matrix exactly once, so the time complexity is proportional to the number of elements in the matrix.

Space Complexity:

O(1)

• We use a fixed amount of extra space (excluding the input and output) for the pointers and directions. The result list is not considered extra space for complexity analysis as it is required by the problem statement.

Code

C++

class Solution {
public:
    vector spiralOrder(vector>& matrix) {
        int rows = matrix.size();
        int cols = matrix[0].size();
        int x = 0;
        int y = 0;
        int dx = 1;
        int dy = 0;
        vector res;
        for (int i = 0; i < rows * cols; ++i) {
            res.push_back(matrix[y][x]);
            matrix[y][x] = -101;
            if (!(0 <= x + dx && x + dx < cols && 0 <= y + dy && y + dy < rows) 
            || matrix[y + dy][x + dx] == -101) {
                int temp = dx;
                dx = -dy;
                dy = temp;
            }
            x += dx;
            y += dy;
        }
        return res;
    }
};

Python

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix or not matrix[0]:
            return []
        rows, cols = len(matrix), len(matrix[0])
        result = []
        x, y = 0, 0
        dx, dy = 1, 0
        for _ in range(rows * cols):
            result.append(matrix[y][x])
            matrix[y][x] = float('inf')
            if not (0 <= x + dx < cols and 0 <= y + dy < rows) or matrix[y + dy][x + dx] == float('inf'):
                dx, dy = -dy, dx
            x += dx
            y += dy
        return result

Java

class Solution {
    public List spiralOrder(int[][] matrix) {
        List res = new ArrayList<>();
        if (matrix == null || matrix.length == 0) return res;
        int rows = matrix.length;
        int cols = matrix[0].length;
        int x = 0, y = 0, dx = 1, dy = 0;
        int totalElements = rows * cols;
        for (int i = 0; i < totalElements; i++) {
            res.add(matrix[y][x]);
            matrix[y][x] = Integer.MIN_VALUE;
            if (!(0 <= x + dx && x + dx < cols && 0 <= y + dy && y + dy < rows) 
            || matrix[y + dy][x + dx] == Integer.MIN_VALUE) {
                int temp = dx;
                dx = -dy;
                dy = temp;
            }
            x += dx;
            y += dy;
        }
        return res;
    }
}

JavaScript

var spiralOrder = function(matrix) {
    const rows = matrix.length;
    const cols = matrix[0].length;
    let x = 0;
    let y = 0;
    let dx = 1;
    let dy = 0;
    const res = [];
    for (let i = 0; i < rows * cols; i++) {
        res.push(matrix[y][x]);
        matrix[y][x] = ".";
        if (!(0 <= x + dx && x + dx < cols && 0 <= y + dy && y + dy < rows)
        || matrix[y+dy][x+dx] === ".") {
            [dx, dy] = [-dy, dx];
        }
        x += dx;
        y += dy;
    }
    return res;    
};