Spiral Matrix - C++ Solution

1. Introduction

In this post, we'll explore a fascinating array problem often referred to as the Spiral Matrix. This problem involves traversing a 2D matrix in a spiral order, starting from the top-left corner and progressively circling toward the center.

Problem

Given an M × N integer matrix, the task is to return its elements in a spiral order. This involves moving right across the top row, down the rightmost column, left across the bottom row, and up the leftmost column, repeatedly closing in towards the center.

2. Solution Steps

1. Initialize four pointers to keep track of the boundaries (top, bottom, left, right).

2. Traverse the matrix in spiral order by iterating over the boundaries.

3. Move right across the top row, increment the top boundary.

4. Move down the rightmost column, decrement the right boundary.

5. Move left across the bottom row, decrement the bottom boundary.

6. Move up the leftmost column, increment the left boundary.

7. Repeat steps 3-6 until all elements are traversed.

3. Code Program

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

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

    vector<int> spiral;
    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++) {
            spiral.push_back(matrix[top][i]);
        }
        top++;

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

        // Make sure we are now on a different row
        if (top <= bottom) {
            // Traverse from right to left
            for (int i = right; i >= left; i--) {
                spiral.push_back(matrix[bottom][i]);
            }
            bottom--;
        }

        // Make sure we are now in a different column
        if (left <= right) {
            // Traverse upwards
            for (int i = bottom; i >= top; i--) {
                spiral.push_back(matrix[i][left]);
            }
            left++;
        }
    }

    return spiral;
}

int main() {
    vector<vector<int>> matrix = {
        { 1, 2, 3, 4, 5},
        {16, 17, 18, 19, 6},
        {15, 24, 25, 20, 7},
        {14, 23, 22, 21, 8},
        {13, 12, 11, 10, 9}
    };

    vector<int> result = spiralOrder(matrix);
    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Explanation:

The function spiralOrder takes a 2D matrix and returns a vector containing the matrix's elements in spiral order. It uses four pointers (top, bottom, left, right) to track the boundaries of the current loop. The function iterates over these boundaries, collecting elements in the specified spiral order. 

For the given matrix, the output is [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25], showcasing the complete spiral traversal of the matrix.