# Spiral Order Traversal

You are given a N x N matrix, you need to perform a spiral order traversal and print the elements of the matrix in that order.

Sample Input: [ [1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16] ]
Expected Output: 1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10

Algorithm

The problem can be solved by dividing the matrix into loops or squares of boundaries

1. Create four pointers R1, C1, R2, C2 and initialize R1 and C1 to 0 and R2 and C2 to (N-1) where NxN is the size of the matrix.
2. Run a while loop till all the squares are covered.
3. Inside the while, run 4 for loops for each boundary. Print the top row from C1 <= c <= C2. Print the last column, from (R1 + 1) <= r <= R2. Print the last row from (C2 – 1) >= c > C1. Print the first column from R2 >= r > R1.
4. Do this until all the squares are covered.
```#include <bits/stdc++.h>
using namespace std;

vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> ans;
if(matrix.size()==0){
return ans;
}
int r1=0, c1=0;
int r2 = matrix.size()-1;
int c2 = matrix.size()-1;
while(r1<=r2 && c1<=c2){
for(int c = c1; c<=c2; c++){
ans.push_back(matrix[r1][c]);
}
for(int r = r1+1; r<=r2; r++){
ans.push_back(matrix[r][c2]);
}
if(r1<r2 && c1<c2){
for(int c = c2-1; c>c1; c--){
ans.push_back(matrix[r2][c]);
}
for(int r = r2; r>r1; r--){
ans.push_back(matrix[r][c1]);
}
}
r1++;
c1++;
r2--;
c2--;
}
return ans;
}

int main(){
vector<vector<int>> matrix(4, vector<int>(4));
int val = 1;
for(int i=0; i<4; i++){
for(int j=0; j<4; j++){
matrix[i][j] = val++;
}
}
vector<int> ans = spiralOrder(matrix);
for(auto i:ans){
cout<<i<<" ";
}
return 0;
}
```

Also, take a look at another popular interview problem Is given a Tree a BST or not?