Start learning free

LESSON 50 OF 321 · MATRIX

Spiral Matrix in C++: Four Shrinking Boundaries in O(m * n)

Practice O(m*n) Read the full explanation

You get a grid matrix of integers, with m rows and n columns.

Return a vector of its values in spiral order.

matrix is a vector of rows. Each row is a vector of integers. Row 0 is the top row. Column 0 is the leftmost column.

The spiral starts at the top-left value and goes clockwise around the edge. It goes right along the top row, then down the right column. Then it goes left along the bottom row and up the left column.

Next, it does the same with the smaller grid inside, and so on. It takes each value exactly once.

 

Example 1:

Input: matrix = [
  [5, 1, 8],
  [0, 3, 2],
  [9, 7, 4]
]
Output: [5, 1, 8, 2, 4, 7, 9, 0, 3]
Explanation: The spiral first goes around the edge:
5, 1 and 8 across the top,
2 and 4 down the right side,
7 and 9 back along the bottom,
0 up the left side.
3 is left in the middle.

Example 2:

Input: matrix = [
  [3, -1, 7],
  [6, 0, 2],
  [1, 5, 9],
  [8, 8, 4]
]
Output: [3, -1, 7, 2, 9, 4, 8, 8, 1, 6, 0, 5]
Explanation: The spiral first goes around the edge:
3, -1 and 7 across the top,
2, 9 and 4 down the right side,
8 and 8 back along the bottom,
1 and 6 up the left side.
Inside, one column is left.
It gives 0, then the 5 below it.

Example 3:

Input: matrix = [
  [-4, 0, 4]
]
Output: [-4, 0, 4]
Explanation: There is only one row.
The spiral goes right along it and stops.
No value is taken twice.

 

Constraints:

  • m and n are each from 1 to 500.
  • Each value is an integer from -1000 to 1000.
  • Negative values and repeats are allowed.

Note:

Your algorithm should run in O(m * n) time: it visits every element once.

STEP 1 OF 19
    Ctrl + Enter to check

    C++ · MATRIX

    Spiral Matrix in C++, explained

    Problem overview

    The method spiralOrder takes a matrix, a vector<vector<int>> with m rows and n columns, and returns a vector<int> with all its elements in spiral order. The spiral starts at the top-left corner and goes clockwise around the outside: the top row left to right, the right column top to bottom, the bottom row right to left, and the left column bottom to top. Then it repeats on the part that is left inside, until every element has been visited exactly once.

    For this matrix:

    1 2 3
    4 5 6
    7 8 9
    

    the result is [1, 2, 3, 6, 9, 8, 7, 4, 5]. The outside ring gives 1, 2, 3, 6, 9, 8, 7, 4, and only 5 is left in the middle. The matrix doesn't have to be square: a 3 by 4 matrix gives [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7], where the inside that remains after one lap is a single row, 6 and 7.

    Approach: four boundaries that move inward

    There is no clever formula here. The task is to simulate the walk without losing track of where you are. Keeping a grid of "visited" flags and turning right at every wall works, but it needs O(m * n) extra memory for the flags.

    A simpler way is to remember the part of the matrix that hasn't been visited yet, as a rectangle with four boundaries: top and bottom are the first and last unvisited rows, left and right the first and last unvisited columns. One lap walks the four sides of that rectangle. After each side is finished, its boundary moves one step inward. When the boundaries cross, nothing is left.

    Every element is added exactly once, so the time is O(m * n), and apart from the result vector the extra space is a few integers.

    The one subtle point is the end of the walk. When the rectangle has shrunk to a single row or a single column, the first two sides already cover everything. Walking the other two would add the same elements again. That is why the last two sides each sit behind an if.

    Step by step

    1. Create an empty vector<int> named result that collects elements in the order they are visited.
    2. Declare top as 0 and bottom as matrix.size() - 1, both int. At the start every row is unvisited.
    3. Declare left as 0 and right as matrix[0].size() - 1. Every row has the same length, so row 0 tells the column count.
    4. Loop while top <= bottom && left <= right. As long as neither pair has crossed, some elements remain. Each pass is one lap.
    5. Walk the top row with col from left to right, both ends included, adding matrix[top][col] with push_back.
    6. Move top down: top++. The top row is done. Doing this now also keeps the top-right corner from being visited again by the next side.
    7. Walk the right column with row from top (already moved) to bottom, adding matrix[row][right].
    8. Move right left: right--.
    9. Check top <= bottom. If only one row was left, it was just walked as the top row, and going back along it would repeat its elements.
    10. Inside that if, walk the bottom row backwards with col from right down to left, adding matrix[bottom][col], then do bottom--.
    11. Check left <= right. If only one column was left, it was just walked as the right column.
    12. Inside that if, walk the left column upwards with row from bottom down to top, adding matrix[row][left], then do left++.
    13. After the while loop, return result.

    The solution in C++

    class Solution {
    public:
        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;
        }
    };
    

    The C++ details worth knowing:

    • size() is unsigned, the boundaries are not. matrix.size() - 1 is computed as an unsigned number and then converted when it is stored in an int. For a non-empty matrix that is the ordinary last index. Keeping top, bottom, left and right as signed ints matters, because the boundaries can step past each other: bottom can reach -1, and a signed comparison like top <= bottom then correctly says "nothing left". An unsigned bottom would wrap to a huge number instead.
    • push_back grows the vector. result starts empty and gains one element per call, so you never index into it.
    • Declaring several variables on one line. int top = 0, bottom = matrix.size() - 1; declares two separate ints, each with its own initial value.
    • matrix[0] needs a non-empty matrix. The constraints guarantee at least one row and one column, so reading matrix[0].size() is safe here.

    Edge cases and common mistakes

    • A single row. {{1, 2, 3}} gives [1, 2, 3]. After the top row, top is 1 and bottom is 0, so the bottom-row if is skipped.
    • A single column. {{3}, {2}, {1}} gives [3, 2, 1]. After the right column, right is -1 and left is 0, so the left-column if is skipped.
    • A single element. {{4}} gives [4].
    • A non-square matrix. {{1, 2}, {3, 4}, {5, 6}} gives [1, 2, 4, 6, 5, 3].
    • Leaving out the two if checks. This is the classic mistake. Without them, the 3 by 4 example returns [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7, 6], with 6 repeated. The single column example returns [3, 2, 1, 2], and the single row returns [1, 2, 3, 2, 1].
    • Updating a boundary after its side is walked, but in the wrong place. If top++ comes after the right column instead of before it, the top-right corner is added twice.
    • Using col < right instead of col <= right. Both boundaries are rows or columns that still hold unvisited elements, so both ends are included.

    Complexity

    Time is O(m * n). Each element is pushed exactly once, and the checks and boundary moves cost O(1) per lap, with at most about min(m, n) / 2 laps.

    Extra space is O(1) apart from result, which holds all m * n elements because it is the output.

    Keep going with C++1,600+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free