Skip to main content

Matrix

Spiral Matrix

Problem Description

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

Problem Explanation

Given an m x n matrix, our task is to traverse and return all elements in a spiral order using a specific pattern of movements. The journey begins at the top-left corner of the matrix, at position [0,0]. From this starting point, we move right across the current row until we reach the last unvisited element. Once we can't move right anymore, we change direction and begin moving downward through the rightmost column until we reach its end. When we can't proceed downward further, we switch direction again, this time moving left across the bottom row until we reach the leftmost unvisited element. After we can't move left anymore, we change direction one final time, moving upward through the leftmost column until we can't go any higher. This complete circuit forms our first layer of traversal.

After completing this outer circuit, we move inward to the next layer. The process repeats itself, but now working with a smaller, inner loop of the matrix. We continue this pattern of right, down, left, and up movements, layer by layer, moving progressively inward until we've visited every element in the matrix. Each direction change is triggered naturally when we reach the boundary of our current layer, ensuring we capture all elements exactly once in our spiral pattern.

Example

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

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]

Constraints

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 10
  • -100 <= matrix[i][j] <= 100

When solving implementation-based problems, the primary focus should be on understanding the process and designing a clear and effective solution. The goal is to stimulate logical thinking and translate it into an intuitive and well-structured implementation. Let’s explore how to approach this

Optimal Approach

Intuition

Picture yourself walking around the edges of a picture frame, but instead of just one loop, imagine that inside the first frame is a slightly smaller frame, and inside that is an even smaller one. This nested structure perfectly represents how we traverse our matrix in spiral order. Just as you would trace the edge of each frame from the outermost to the innermost, we trace the elements of our matrix layer by layer.

The elegance of our solution lies in how we manage these layers using just four boundary variables. These variables—top, right, bottom, and left—act as our guides, telling us exactly where the current "frame" or layer begins and ends. Think of them as adjustable boundaries that help us keep track of which elements we still need to visit. What makes this approach particularly clever is how these boundaries naturally shrink after we complete each side of the current layer. When we finish processing the top row, we move the top boundary down by one. After completing the rightmost column, we move the right boundary inward by one. Similarly, after processing the bottom row, we move the bottom boundary up, and after the leftmost column, we move the left boundary inward.

This natural shrinking of boundaries creates what we might call a peeling-the-onion effect. Just as you might peel an onion layer by layer from the outside in, we process our matrix from its outer elements progressively inward. Each time we complete a circuit, our boundaries adjust to focus our attention on the next inner layer. This process continues smoothly until our boundaries cross each other (when the top becomes greater than the bottom, or the left becomes greater than the right), signaling that we've processed every element in the matrix. The beauty of this approach is its simplicity - we don't need to keep track of visited elements or maintain complex direction logic. Our four boundary variables naturally guide us through the entire matrix in perfect spiral order, making the solution both elegant and efficient.

Approach

Initialize Boundaries:Set top = 0 and left = 0.Set bottom = number of rows - 1 and right = number of columns - 1.Create an empty list result to store the elements in spiral order.

Loop Until Boundaries Overlap:Continue the loop while top <= bottom and left <= right.

Traverse From Left to Right (Top Row):Iterate from left to right and add each element of matrix[top][i] to result.Increment top to move the top boundary downward.

Traverse From Top to Bottom (Right Column):Iterate from top to bottom and add each element of matrix[i][right] to result.Decrement right to move the right boundary leftward.

Traverse From Right to Left (Bottom Row):If top <= bottom, iterate from right to left and add each element of matrix[bottom][i] to result.Decrement bottom to move the bottom boundary upward.

Traverse From Bottom to Top (Left Column):If left <= right, iterate from bottom to top and add each element of matrix[i][left] to result.Increment left to move the left boundary rightward.

Return the Result:After the loop ends, return the result list containing the elements in spiral order.

Dry Run

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

Initial Boundaries:

  • top = 0, bottom = 2, left = 0, right = 2
  • result = []

First Iteration:

  • Traverse from left to right on the top row: Add 1, 2, 3 to result → [1, 2, 3].
    Update top = 1 (move the top boundary down).
  • Traverse from top to bottom on the right column: Add 6, 9 to result → [1, 2, 3, 6, 9].
    Update right = 1 (move the right boundary left).
  • Traverse from right to left on the bottom row: Add 8, 7 to result → [1, 2, 3, 6, 9, 8, 7].
    Update bottom = 1 (move the bottom boundary up).
  • Traverse from bottom to top on the left column: Add 4 to result → [1, 2, 3, 6, 9, 8, 7, 4].
    Update left = 1 (move the left boundary right).

Second Iteration:

  • Traverse from left to right on the middle row: Add 5 to result → [1, 2, 3, 6, 9, 8, 7, 4, 5].
    Update top = 2.

Exit Condition:

  • top > bottom (2 > 1), so the loop ends.

Final Output:
result = [1, 2, 3, 6, 9, 8, 7, 4, 5]

Code for All Languages
C++
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {

        // Initialize boundaries for traversal
        int top = 0;
        int left = 0;
        int right = matrix[0].size() - 1;
        int bottom = matrix.size() - 1;

        // Result vector to store spiral order elements
        vector<int> ans;

        // Loop until all rows and columns are traversed
        while (top <= bottom && left <= right) {

            // Traverse from left to right on the top row
            for (int i = left; i <= right; i++) {
                ans.push_back(matrix[top][i]);
            }
            top++; // Move top boundary down

            // Traverse from top to bottom on the right column
            for (int i = top; i <= bottom; i++) {
                ans.push_back(matrix[i][right]);
            }
            right--; // Move right boundary left

            // Check if rows are remaining and traverse from right to left on the bottom row
            if (top <= bottom) {
                for (int i = right; i >= left; i--) {
                    ans.push_back(matrix[bottom][i]);
                }
                bottom--; // Move bottom boundary up
            }

            // Check if columns are remaining and traverse from bottom to top on the left column
            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    ans.push_back(matrix[i][left]);
                }
                left++; // Move left boundary right
            }
        }
        return ans;
    }
};

Java
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {

        // Initialize boundaries
        int top = 0;
        int left = 0;
        int right = matrix[0].length - 1;
        int bottom = matrix.length - 1;

        // Result list to store spiral order elements
        List<Integer> ans = new ArrayList<>();

        // Loop until all rows and columns are traversed
        while (top <= bottom && left <= right) {
            // Traverse from left to right on the top row
            for (int i = left; i <= right; i++) {
                ans.add(matrix[top][i]);
            }
            top++; // Move top boundary down

            // Traverse from top to bottom on the right column
            for (int i = top; i <= bottom; i++) {
                ans.add(matrix[i][right]);
            }
            right--; // Move right boundary left

            // Check if rows are remaining and traverse from right to left on the bottom row
            if (top <= bottom) {
                for (int i = right; i >= left; i--) {
                    ans.add(matrix[bottom][i]);
                }
                bottom--; // Move bottom boundary up
            }

            // Check if columns are remaining and traverse from bottom to top on the left column
            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    ans.add(matrix[i][left]);
                }
                left++; // Move left boundary right
            }
        }
        return ans;
    }
}

Python
class Solution:
    def spiralOrder(self, matrix):

        # Initialize boundaries
        top, left = 0, 0
        right = len(matrix[0]) - 1
        bottom = len(matrix) - 1

        # Result list to store spiral order elements
        ans = []

        # Loop until all rows and columns are traversed
        while top <= bottom and left <= right:
            # Traverse from left to right on the top row
            for i in range(left, right + 1):
                ans.append(matrix[top][i])
            top += 1  # Move top boundary down

            # Traverse from top to bottom on the right column
            for i in range(top, bottom + 1):
                ans.append(matrix[i][right])
            right -= 1  # Move right boundary left

            # Check if rows are remaining and traverse from right to left on the bottom row
            if top <= bottom:
                for i in range(right, left - 1, -1):
                    ans.append(matrix[bottom][i])
                bottom -= 1  # Move bottom boundary up

            # Check if columns are remaining and traverse from bottom to top on the left column
            if left <= right:
                for i in range(bottom, top - 1, -1):
                    ans.append(matrix[i][left])
                left += 1  # Move left boundary right

        return ans

Javascript
class Solution {
    spiralOrder(matrix) {

        // Initialize boundaries
        let top = 0, left = 0;
        let right = matrix[0].length - 1;
        let bottom = matrix.length - 1;

        // Result array to store spiral order elements
        const ans = [];

        // Loop until all rows and columns are traversed
        while (top <= bottom && left <= right) {
            // Traverse from left to right on the top row
            for (let i = left; i <= right; i++) {
                ans.push(matrix[top][i]);
            }
            top++; // Move top boundary down

            // Traverse from top to bottom on the right column
            for (let i = top; i <= bottom; i++) {
                ans.push(matrix[i][right]);
            }
            right--; // Move right boundary left

            // Check if rows are remaining and traverse from right to left on the bottom row
            if (top <= bottom) {
                for (let i = right; i >= left; i--) {
                    ans.push(matrix[bottom][i]);
                }
                bottom--; // Move bottom boundary up
            }

            // Check if columns are remaining and traverse from bottom to top on the left column
            if (left <= right) {
                for (let i = bottom; i >= top; i--) {
                    ans.push(matrix[i][left]);
                }
                left++; // Move left boundary right
            }
        }
        return ans;
    }
}

Time Complexity : O(m*n)

The time complexity of the spiral order traversal algorithm is determined by how many elements it processes and how many iterations are required to cover the entire matrix. The algorithm visits each element of the matrix exactly once. At each step, it processes a boundary of the matrix, either traversing the top row, the right column, the bottom row, or the left column.

After processing a boundary, the algorithm adjusts either the top or bottom boundary to reduce the number of rows, and the left or right boundary to reduce the number of columns. This continues until all elements have been traversed. Since there are a total of m * n elements in an m x n matrix, the algorithm iterates over each element exactly once.

Therefore, the time complexity of this algorithm is O(m * n), where m represents the number of rows and n represents the number of columns. This means the algorithm's runtime scales linearly with the number of elements in the matrix.

Space Complexity : O(1)

Auxiliary Space Complexity: The algorithm uses a few variables (top, bottom, left, right) for managing boundaries and temporary variables for indexing. These are all constant space usages. 

Therefore, the auxiliary space complexity is O(1), meaning the algorithm uses constant extra space beyond the input and output.

Total Space Complexity: The only significant space usage comes from the matrix itself and the output list ans that stores the elements in spiral order. The size of ans is proportional to the number of elements in the matrix, i.e., m * n. Since the matrix is given as input, we don't count it as additional space.
Hence, the total space is dominated by the result list, which requires
O(m * n) space.


Learning Tip

Now we have successfully tackled this problem, let's try these similar problems.

Given a positive integer n, generate an n x n matrix filled with elements from 1 to n^2 in spiral order.

Given an m x n matrix mat, return an array of all the elements of the array in a diagonal order.