Spiral Traversal on a Matrix

Understanding the Problem

The goal is to traverse a matrix in a spiral order.

Method 1: Using Iterative Approach

This method uses an iterative approach to traverse the matrix in spiral order.

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

void spiralTraversal(int matrix[][100], int rows, int cols) {
    int top = 0, bottom = rows - 1, left = 0, right = cols - 1;

    while (top <= bottom && left <= right) {
        for (int i = left; i <= right; i++) {
            cout << matrix[top][i] << " ";
        }
        top++;

        for (int i = top; i <= bottom; i++) {
            cout << matrix[i][right] << " ";
        }
        right--;

        if (top <= bottom) {
            for (int i = right; i >= left; i--) {
                cout << matrix[bottom][i] << " ";
            }
            bottom--;
        }

        if (left <= right) {
            for (int i = bottom; i >= top; i--) {
                cout << matrix[i][left] << " ";
            }
            left++;
        }
    }
}

int main() {
    int matrix[100][100] = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12},
        {13, 14, 15, 16}
    };
    int rows = 4, cols = 4;
    cout << "Spiral Traversal: ";
    spiralTraversal(matrix, rows, cols);
    cout << endl;
    return 0;
}
            

Output:

Spiral Traversal: 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

Method 2: Using Recursion

This method uses recursion to achieve spiral traversal.

#include <iostream>
using namespace std;

void spiralUtil(int matrix[][100], int top, int bottom, int left, int right) {
    if (top > bottom || left > right) return;

    for (int i = left; i <= right; i++) {
        cout << matrix[top][i] << " ";
    }
    top++;

    for (int i = top; i <= bottom; i++) {
        cout << matrix[i][right] << " ";
    }
    right--;

    if (top <= bottom) {
        for (int i = right; i >= left; i--) {
            cout << matrix[bottom][i] << " ";
        }
        bottom--;
    }

    if (left <= right) {
        for (int i = bottom; i >= top; i--) {
            cout << matrix[i][left] << " ";
        }
        left++;
    }

    spiralUtil(matrix, top, bottom, left, right);
}

void spiralTraversal(int matrix[][100], int rows, int cols) {
    spiralUtil(matrix, 0, rows - 1, 0, cols - 1);
}

int main() {
    int matrix[100][100] = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12},
        {13, 14, 15, 16}
    };
    int rows = 4, cols = 4;
    cout << "Spiral Traversal: ";
    spiralTraversal(matrix, rows, cols);
    cout << endl;
    return 0;
}
            

Output:

Spiral Traversal: 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10