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.
Comments
Post a Comment