Spiral Matrix

Traversing a Matrix in Spiral Order

Traversing a matrix in spiral order is a common problem in programming, where the goal is to extract all elements of a matrix following a specific pattern.

The traversal begins at the top-left corner and proceeds in a clockwise spiral until all elements are covered.

Pair with given sum - Two Sum

Problem Statement

You are given a rectangular matrix of integers with dimensions m×nm \times n. The task is to return a list containing all the elements of the matrix arranged in spiral order.

This means traversing the matrix in a clockwise spiral pattern, starting from the top-left corner.

Constraints:

  • 1 <= matrix.length, matrix[i].length <= 10
  • -100 <= matrix[i][j] <= 100
Sprial Matrix 2

There are mainly 3 approach to solve this problem – 

  1. Recursion
  2. Iteration
  3. Iteration (Optimal)

1. Recursion

  • Time complexity: O(m∗n)
  • Space complexity: O(min(m,n))

Where m is the number of rows and n is the number of columns.

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        m, n = len(matrix), len(matrix[0])
        res = []

        # append all the elements in the given direction
        def dfs(row, col, r, c, dr, dc):
            if row == 0 or col == 0:
                return
            
            for i in range(col):
                r += dr
                c += dc
                res.append(matrix[r][c])

            # sub-problem
            dfs(col, row - 1, r, c, dc, -dr)
        
        # start by going to the right
        dfs(m, n, 0, -1, 0, 1)
        return res

2. Iteration

Time & Space Complexity
    • Time complexity: O(m∗n)
    • Space complexity: O(1)

Where m is the number of rows and n is the number of columns.

Code

class Solution {
public:
    vector spiralOrder(vector>& matrix) {
        vector res;
        int left = 0, right = matrix[0].size();
        int top = 0, bottom = matrix.size();

        while (left < right && top < bottom) {
            for (int i = left; i < right; i++) {
                res.push_back(matrix[top][i]);
            }
            top++;
            for (int i = top; i < bottom; i++) {
                res.push_back(matrix[i][right - 1]);
            }
            right--;
            if (!(left < right && top < bottom)) {
                break;
            }
            for (int i = right - 1; i >= left; i--) {
                res.push_back(matrix[bottom - 1][i]);
            }
            bottom--;
            for (int i = bottom - 1; i >= top; i--) {
                res.push_back(matrix[i][left]);
            }
            left++;
        }

        return res;
    }
};

3. Iteration (Optimal)

  • Time complexity: O(m∗n)
  • Space complexity: O(1)

Where m is the number of rows and n is the number of columns.

Code

class Solution {
public:
    vector spiralOrder(vector>& matrix) {
        vector res;
        vector> directions = {{0, 1}, {1, 0}, 
                                             {0, -1}, {-1, 0}};
        vector steps = {matrix[0].size(), matrix.size() - 1};

        int r = 0, c = -1, d = 0;
        while (steps[d % 2]) {
            for (int i = 0; i < steps[d % 2]; i++) {
                r += directions[d].first;
                c += directions[d].second;
                res.push_back(matrix[r][c]);
            }
            steps[d % 2]--;
            d = (d + 1) % 4;
        }
        return res;
    }
};

More Articles