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

- 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.
- Run a while loop till all the squares are covered.
- 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.
- 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[0].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?*

## One comment