matrix spiral printing in C++

Problem statement

Given a matrix of r rows and c columns, print the matrix in spiral form with C++ program.

Example:

11 12 13 14 15

16 17 18 19 20

21 22 23 24 25

26 27 28 29 30

31 32 33 34 35

Output:

11 12 13 14 15 20 25 30 35 34 33 32 31 26 21 16 17 18 19 24 29 28 27 22 23
Visualization:

Approach:

If we carefully analyze the spiral pattern, then it can be observed that firstly the elements present at boundary of the matrix are printed in clockwise direction then same process continues for inner boundaries of matrix.

To solve, this problem break matrix into four loops:

  • ¬†First loop to print current top row. Iterate from current first column to current last column and then increment current top row by 1 position.
  • Second loop to print current last column. Iterate from current top row to current bottom row and then decrement current last column by 1 position.
  • Third loop to print current bottom row. Iterate from current last column to current first column and then decrement the current bottom row by 1 position.
  • Fourth loop to print current first column. Iterate from current bottom row to current top row and then increment current first row by 1 position.

Important observation:

  1. Stop iterating through above four for loops when either current last column becomes lesser than current first column or when current top row becomes greater than current bottom row.
  2. if we analyze carefully, it is found that when the size of matrix is odd like 3*3 or 5*5 and the no of rows and columns are not equal like 3*5 or 5*3, then some inner elements are redundantly printed. So, to avoid that, we have to use extra 2 conditions into last two for loops.
  3. In 3rd for loop, the condition has to be applied that, if current bottom row >= current top row, then only run the 3rd loop, otherwise ignore it.
  4. For fourth loop should only run when current left column <= current last column.
#include<bits/stdc++.h>
using namespace std;
vector<int> spirallyTraverse(vector<vector<int> > matrix, int r, int c)
{
    --r; --c;
    int tr = 0, lc = 0;
    vector<int>v;
    while (lc <= c && tr <= r)
    {
        for (int i = lc; i <= c; ++i)
        {
            v.push_back(matrix[tr][i]);
        }
        tr++;
        for (int i = tr; i <= r; ++i)
        {
            v.push_back(matrix[i][c]);
        }
        --c;
        if (tr <= r)
        {
            for (int i = c; i >= lc; --i)
            {
                v.push_back(matrix[r][i]);
            }
            --r;
        }
        if (lc <= c)
        {
            for (int i = r; i >= tr; --i)
            {
                v.push_back(matrix[i][lc]);
            }
            ++lc;
        }
    }
    return v;
}

int main()
{
    int r, c;
    cin >> r >> c;
    vector<vector<int>> matrix;
    for (int i = 0; i < r; i++)
    {
        int x; vector<int> v;
        for (int i = 0; i < c; i++)
        {
            cin >> x;
            v.push_back(x);
        }
        matrix.push_back(v);
    }
    vector<int>v = spirallyTraverse(matrix, r, c) ;
    for (int i = 0; i < v.size(); ++i)
        cout << v[i] << ", ";
    return 0;
}

If this post added any value to your algorithmic knowledge, please share your valuable feedback. Thank you!

 

Leave a Reply

Your email address will not be published. Required fields are marked *