Spiral Traversal of Matrix | Print Matrix in Spiral Form

Traversing a matrix in a specific pattern can be a common task that every programmer should know about. One such traversal pattern is the spiral traversal of a 2x2 matrix, which we will delve in this article, and explore different approaches to implement it.

What is the Spiral Traversal of a Matrix?

Spiral traversal of a matrix refers to the process of visiting all the elements of the matrix in a spiral order, starting from the top-left corner and moving in a clockwise direction until all elements are covered. The traversal moves along the outer boundaries of the matrix in a spiral pattern, gradually moving towards the center.

To understand the spiral traversal algorithm, let's consider a simple example matrix:

The spiral traversal of this matrix would be: 1 2 3 4 8 12 11 10 9 5 6 7 The traversal starts from the top-left corner and moves along the outer boundary of the matrix in a clockwise direction.

How to do Spiral Traversal of a Matrix?

There are several methods to achieve spiral traversal of a matrix. Here are a few commonly used methods:

Method 1) Iterative Approach with Boundary Tracking

One of the most straightforward methods for spiral traversal involves tracking the boundaries of the matrix as we move along the spiral. The steps involved in this approach are as follows:

1. Initialize four variables: topRow, bottomRow, leftCol, and rightCol to represent the boundaries of the current spiral level.
2. Use a while loop to iterate while the topRow is less than or equal to the bottomRow and the leftCol is less than or equal to the rightCol.
3. Traverse the top row from leftCol to rightCol, incrementing topRow afterward.
4. Traverse the right column from topRow to bottomRow, decrementing rightCol afterward.
5. Check if there are remaining rows (topRow <= bottomRow) and traverse the bottom row from rightCol to leftCol, decrementing bottomRow afterward.
6. Check if there are remaining columns (leftCol <= rightCol) and traverse the left column from bottomRow to topRow, incrementing leftCol afterward.
7. Repeat steps 3 to 6 until all elements have been traversed.
8. Store the traversed elements or perform any required operations.

Here is the implementation in C++:

#include <iostream>
#include <vector>
using namespace std;

vector<int> spiralTraversal(vector<vector<int>>& matrix) {
    vector<int> result;
    if (matrix.empty()) {
        return result;
    }

    int rows = matrix.size();
    int cols = matrix[0].size();
    int topRow = 0, bottomRow = rows - 1, leftCol = 0, rightCol = cols - 1;

    while (topRow <= bottomRow && leftCol <= rightCol) {
        // Traverse top row
        for (int col = leftCol; col <= rightCol; col++) {
            result.push_back(matrix[topRow][col]);
        }
        topRow++;

        // Traverse right column
        for (int row = topRow; row <= bottomRow; row++) {
            result.push_back(matrix[row][rightCol]);
        }
        rightCol--;

        // Check if there are remaining rows and traverse bottom row
        if (topRow <= bottomRow) {
            for (int col = rightCol; col >= leftCol; col--) {
                result.push_back(matrix[bottomRow][col]);
            }
            bottomRow--;
        }

        // Check if there are remaining columns and traverse left column
        if (leftCol <= rightCol) {
            for (int row = bottomRow; row >= topRow; row--) {
                result.push_back(matrix[row][leftCol]);
            }
            leftCol++;
        }
    }

    return result;
}

int main() {
    vector<vector<int>> matrix = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };

    vector<int> spiral = spiralTraversal(matrix);

    cout << "Spiral order matrix: ";
    for (int num : spiral) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Output:

Spiral order matrix: 1 2 3 6 9 8 7 4 5 

The time complexity of this approach is O(m * n), where m is the number of rows and n is the number of columns in the matrix. We need to visit each element of the matrix once to perform the traversal. The space complexity is O(1) since we are not using any additional data structures that scale with the input size.

But if you have got this question in your assignment and need some more explanation, you can connect with our experts for C++ homework help online.

Method 2) Recursive Approach

The spiral traversal of a matrix can also be achieved using a recursive approach. The steps involved in this method are as follows:

1. Define a recursive function that takes the matrix, the current row and column indices, and the current direction of traversal as parameters.
2. Base case: If all elements have been visited, return from the function.
3. Traverse the current row/column in the given direction, printing or storing the elements.
4. Update the row and column indices based on the direction of traversal.
5. Change the direction of traversal (e.g., clockwise: right -> down -> left -> up) and call the recursive function with the updated indices and direction.
6. Repeat steps 2 to 5 until all elements have been visited.

Here is the C++ code for the recursive approach for spiral traversal:

#include <iostream>
#include <vector>
using namespace std;

void spiralTraversalRecursive(vector<vector<int>>& matrix, int rowStart, int rowEnd, int colStart, int colEnd, vector<int>& result) {
    // Base case: If all elements have been visited
    if (rowStart > rowEnd || colStart > colEnd) {
        return;
    }

    // Traverse top row
    for (int col = colStart; col <= colEnd; col++) {
        result.push_back(matrix[rowStart][col]);
    }
    rowStart++;

    // Traverse right column
    for (int row = rowStart; row <= rowEnd; row++) {
        result.push_back(matrix[row][colEnd]);
    }
    colEnd--;

    // Check if there are remaining rows and traverse bottom row
    if (rowStart <= rowEnd) {
        for (int col = colEnd; col >= colStart; col--) {
            result.push_back(matrix[rowEnd][col]);
        }
        rowEnd--;
    }

    // Check if there are remaining columns and traverse left column
    if (colStart <= colEnd) {
        for (int row = rowEnd; row >= rowStart; row--) {
            result.push_back(matrix[row][colStart]);
        }
        colStart++;
    }

    // Recursive call with updated boundaries
    spiralTraversalRecursive(matrix, rowStart, rowEnd, colStart, colEnd, result);
}

vector<int> spiralTraversal(vector<vector<int>>& matrix) {
    vector<int> result;
    if (matrix.empty()) {
        return result;
    }

    int rows = matrix.size();
    int cols = matrix[0].size();

    spiralTraversalRecursive(matrix, 0, rows - 1, 0, cols - 1, result);

    return result;
}

int main() {
    vector<vector<int>> matrix = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };

    vector<int> spiral = spiralTraversal(matrix);

    cout << "Spiral order matrix: ";
    for (int num : spiral) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Output:

Spiral order matrix: 1 2 3 6 9 8 7 4 5 

The time complexity of the recursive approach is also O(m * n), where m is the number of rows and n is the number of columns in the matrix. The space complexity is O(m * n) in the worst case. This is due to the recursive calls, which create additional function call stacks for each recursive invocation. The space required is proportional to the number of elements in the matrix.

Method 3) Using Layer-by-Layer Approach

This method involves traversing the matrix layer by layer, starting from the outermost layer and moving towards the center. The steps involved in this approach are as follows:

1. Initialize a variable layer to represent the current layer.
2. Use a while loop to iterate until the layer reaches the center of the matrix.
3. Traverse the top row of the current layer.
4. Traverse the right column of the current layer.
5. Traverse the bottom row of the current layer.
6. Traverse the left column of the current layer.
7. Increment layer to move to the next inner layer.
8. Repeat steps 3 to 7 until all layers have been traversed.

These are just a few methods for achieving spiral traversal of a matrix. Each method has its advantages and may be suitable for different scenarios or programming preferences. Choose the method that best suits your requirements and implement it in your preferred programming language.

Below is the C++ code:

#include <iostream>
#include <vector>
using namespace std;

vector<int> spiralTraversal(vector<vector<int>>& matrix) {
    vector<int> result;
    if (matrix.empty()) {
        return result;
    }

    int rows = matrix.size();
    int cols = matrix[0].size();
    int layer = 0;

    while (layer <= rows / 2 && layer <= cols / 2) {
        // Traverse top row
        for (int col = layer; col < cols - layer; col++) {
            result.push_back(matrix[layer][col]);
        }

        // Traverse right column
        for (int row = layer + 1; row < rows - layer; row++) {
            result.push_back(matrix[row][cols - layer - 1]);
        }

        // Check if there are remaining rows and traverse bottom row
        if (layer < rows - layer - 1) {
            for (int col = cols - layer - 2; col >= layer; col--) {
                result.push_back(matrix[rows - layer - 1][col]);
            }
        }

        // Check if there are remaining columns and traverse left column
        if (layer < cols - layer - 1) {
            for (int row = rows - layer - 2; row > layer; row--) {
                result.push_back(matrix[row][layer]);
            }
        }

        layer++;
    }

    return result;
}

int main() {
    vector<vector<int>> matrix = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };

    vector<int> spiral = spiralTraversal(matrix);

    cout << "Spiral order matrix: ";
    for (int num : spiral) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Output:

Spiral order matrix: 1 2 3 6 9 8 7 4 5

The time complexity for this method is O(m * n), where m is the number of rows and n is the number of columns in the matrix. We need to visit each element once to perform the traversal. The space complexity is O(1) since we are not using any additional data structures that scale with the input size.

Conclusion

In this article, we learned about the Spiral Traversal of a Matrix using the iterative, recursive, and Layer-by-Layer approach. Also, learn how to print a 2D Array in Java using 4 different methods.