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[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

Leave a Reply

Your email address will not be published.