Table of contents

Traverse a Matrix in Spiral Order

Given an M x N matrix, traverse the matrix in a spiral order and return the elements in a single list. The traversal should start from the top-left corner, move right, then down, then left, then up, and repeat until all elements have been visited.

Input/Output Examples

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

Output: [1, 2, 3, 6, 9, 8, 7, 4, 5]
Explanation: The matrix is traversed in spiral order as shown above.

Example 2:
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]
Explanation: The matrix is traversed in spiral order as shown above.

Approach to Spirally Traverse a Matrix

  1. Initialize Boundary Pointers:
    • Set up four pointers to define the current boundaries of the spiral traversal: top, bottom, left, and right.
  2. Traverse the Matrix in Spiral Order:
    • Move from left to right across the top boundary and increment the top pointer.
    • Move from top to bottom along the right boundary and decrement the right pointer.
    • Move from right to left across the bottom boundary (if top <= bottom) and decrement the bottom pointer.
    • Move from bottom to top along the left boundary (if left <= right) and increment the left pointer.
    • Repeat these steps until all elements are traversed.
  3. Collect Elements in Order:
    • As you traverse each boundary, collect elements in a list which will contain the matrix elements in spiral order.

C++ Program to Spirally Traverse a Matrix

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

// Function to traverse the matrix in spiral order
vector<int> spiralOrder(const vector<vector<int>>& matrix) {
    vector<int> result;
    if (matrix.empty()) return result;

    int top = 0, bottom = matrix.size() - 1;
    int left = 0, right = matrix[0].size() - 1;

    while (top <= bottom && left <= right) {
        // Traverse from left to right
        for (int i = left; i <= right; i++) {
            result.push_back(matrix[top][i]);
        }
        top++;

        // Traverse from top to bottom
        for (int i = top; i <= bottom; i++) {
            result.push_back(matrix[i][right]);
        }
        right--;

        // Traverse from right to left
        if (top <= bottom) {
            for (int i = right; i >= left; i--) {
                result.push_back(matrix[bottom][i]);
            }
            bottom--;
        }

        // Traverse from bottom to top
        if (left <= right) {
            for (int i = bottom; i >= top; i--) {
                result.push_back(matrix[i][left]);
            }
            left++;
        }
    }

    return result;
}

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

    vector<int> result = spiralOrder(matrix);

    cout << "Spiral Order: ";
    for (int val : result) {
        cout << val << " ";
    }
    cout << endl;

    return 0;
}

Java Program to Spirally Traverse a Matrix

java
import java.util.*;

public class SpiralMatrix {

    // Function to traverse the matrix in spiral order
    public static List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        if (matrix.length == 0) return result;

        int top = 0, bottom = matrix.length - 1;
        int left = 0, right = matrix[0].length - 1;

        while (top <= bottom && left <= right) {
            // Traverse from left to right
            for (int i = left; i <= right; i++) {
                result.add(matrix[top][i]);
            }
            top++;

            // Traverse from top to bottom
            for (int i = top; i <= bottom; i++) {
                result.add(matrix[i][right]);
            }
            right--;

            // Traverse from right to left
            if (top <= bottom) {
                for (int i = right; i >= left; i--) {
                    result.add(matrix[bottom][i]);
                }
                bottom--;
            }

            // Traverse from bottom to top
            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    result.add(matrix[i][left]);
                }
                left++;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9}
        };

        List<Integer> result = spiralOrder(matrix);

        System.out.println("Spiral Order: " + result);
    }
}

Python Program to Spirally Traverse a Matrix

python
# Function to traverse the matrix in spiral order
def spiral_order(matrix):
    result = []
    if not matrix:
        return result

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

    while top <= bottom and left <= right:
        # Traverse from left to right
        for i in range(left, right + 1):
            result.append(matrix[top][i])
        top += 1

        # Traverse from top to bottom
        for i in range(top, bottom + 1):
            result.append(matrix[i][right])
        right -= 1

        # Traverse from right to left
        if top <= bottom:
            for i in range(right, left - 1, -1):
                result.append(matrix[bottom][i])
            bottom -= 1

        # Traverse from bottom to top
        if left <= right:
            for i in range(bottom, top - 1, -1):
                result.append(matrix[i][left])
            left += 1

    return result

# Example usage
if __name__ == "__main__":
    matrix = [
        [1, 2, 3],
        [4, 5, 6],
        [7, 8, 9]
    ]
    
    result = spiral_order(matrix)
    print("Spiral Order:", result)
  • Time Complexity: O(M * N) where M is the number of rows and N is the number of columns, as each element is visited once.
  • Space Complexity: O(1) if we exclude the space for the output list, as no additional space proportional to the input size is used for traversal.

DSA

Related Articles