Print Matrix in Spiral Order

Given a matrix, print all elements in spiral order.

Example 1

Input: matrix = [[0, 1, 2], [3, 4, 5], [6, 7, 8], [9, 10, 11]]
Output: [0, 1, 2, 5, 8, 11, 10, 9, 6, 3, 4, 7]
Explanation: We are traversing this matrix spirally:
0 1 2
3 4 5
6 7 8
9 10 11

Approach: Using 4 Variables for Traversal

Intuition

This problem is similar to Generate Spiral Matrix. However, in the said problem, the output matrix will always be a square one and thus all the following 4 steps will be completed in each layer of traversal:

traversing from top left to top right (first row in the layer)
traversing from top right to bottom right (last column in the layer)
traversing from bottom right to bottom left (last row in the layer) and,
traversing from bottom left to top left (first column in the layer)

However for this problem, some matrices exist where only the first 2 steps are required for the last layer of traversal and thus we need to add two conditions such that the last 2 steps are not duplicated for the last layer of traversal.

Implementation

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    int n = matrix.size(), m = matrix[0].size();
    int rowStart = 0, rowEnd = n - 1, columnStart = 0, columnEnd = m - 1;
    vector<int> spiralOrderTraversal;
    while (rowStart <= rowEnd and columnStart <= columnEnd) {
        // traversing from top left to top right (first row in the layer)
        for (int c = columnStart; c <= columnEnd; ++c) {
            spiralOrderTraversal.push_back(matrix[rowStart][c]);
        }
        ++rowStart;
        // traversing from top right to bottom right (last column in the layer)
        for (int r = rowStart; r <= rowEnd; ++r) {
            spiralOrderTraversal.push_back(matrix[r][columnEnd]);
        }
        --columnEnd;
        // traversing from bottom right to bottom left (last row in the layer)
        // note the condition below
        if (rowStart <= rowEnd) {
            for (int c = columnEnd; c >= columnStart; --c) {
                    spiralOrderTraversal.push_back(matrix[rowEnd][c]);
            }
        }
        --rowEnd;
        // traversing from bottom left to top left (first column in the layer)
        // note the condition below
        if (columnStart <= columnEnd) {
            for (int r = rowEnd; r >= rowStart; --r) {
                spiralOrderTraversal.push_back(matrix[r][columnStart]);
            }
        }
        ++columnStart;
    }
    return spiralOrderTraversal;
}

We can also achieve the same spiral order traversal using recursion:

void traverseLayer(int rowStart, int rowEnd, int columnStart, int columnEnd, vector<int> &spiralOrderTraversal, vector<vector<int>> &matrix) {
    if (rowStart > rowEnd) return;
    // traversing from top left to top right (first row in the layer)
    for (int c = columnStart; c <= columnEnd; ++c) {
        spiralOrderTraversal.push_back(matrix[rowStart][c]);
    }
    ++rowStart;
    if (columnStart > columnEnd) return;
    // traversing from top right to bottom right (last column in the layer)
    for (int r = rowStart; r <= rowEnd; ++r) {
        spiralOrderTraversal.push_back(matrix[r][columnEnd]);
    }
    --columnEnd;
    // traversing from bottom right to bottom left (last row in the layer)
    // note the condition below
    if (rowStart > rowEnd) return;
    for (int c = columnEnd; c >= columnStart; --c) {
            spiralOrderTraversal.push_back(matrix[rowEnd][c]);
    }
    --rowEnd;
    // traversing from bottom left to top left (first column in the layer)
    // note the condition below
    if (columnStart > columnEnd) return;
    for (int r = rowEnd; r >= rowStart; --r) {
        spiralOrderTraversal.push_back(matrix[r][columnStart]);
    }
    ++columnStart;
    traverseLayer(rowStart, rowEnd, columnStart, columnEnd, spiralOrderTraversal, matrix);
}
vector<int> spiralOrder(vector<vector<int>>& matrix) {
    int n = matrix.size(), m = matrix[0].size();
    int rowStart = 0, rowEnd = n - 1, columnStart = 0, columnEnd = m - 1;
    vector<int> spiralOrderTraversal;
    traverseLayer(rowStart, rowEnd, columnStart, columnEnd, spiralOrderTraversal, matrix);
    return spiralOrderTraversal;
}

Complexity Analysis

Time Complexity: $O(N * M)$ , where $N =$ number of rows, $M =$ number of columns.
Space Complexity: $O(1)$ extra, if the returned vector is considered, space complexity is $O(N * M)$ .

Published 22 Dec 2020

CS Posts on Twitter