DEV Community

loading...

Generate a spiral order matrix

ats1999 profile image Rahul kumar ・1 min read

Given an integer A, generate a square matrix filled with elements from 1 to A2 in spiral order.

See problem at leetcode

For example:

A = 2
Enter fullscreen mode Exit fullscreen mode

Then matrix would be

1 2 
4 3
Enter fullscreen mode Exit fullscreen mode
A = 3
Enter fullscreen mode Exit fullscreen mode

Then matrix would be

1 2 3
8 9 4
7 6 5
Enter fullscreen mode Exit fullscreen mode

Idea

To generate the spiral order matrix, you should traverse the matrix layer by layer. First, generate the outer layer, then generate the one layer down, and so on.

Here, I have used 4 variable to track the row and column which we would like to fill.

  1. row-1
  2. column-n
  3. row-n
  4. column-1
  5. row-2
  6. column-(n-1)
  7. row-(n-1) ..... ..... and so on
vector<vector<int> > Solution::generateMatrix(int A) {
    vector<vector<int>>ans(A,vector<int>(A,0));

    int rowBegin = 0;
    int colBegin = 0;
    int rowEnd = A-1;
    int colEnd = A-1;
    int counter = 1;

    while(rowBegin<=rowEnd && colBegin<=colEnd){
        // top left to top right
        for(int i=colBegin; i<=colEnd; i++)
            ans[rowBegin][i] = counter++; 
        rowBegin++;

        // top right to bottom right
        for(int i=rowBegin; i<=rowEnd; i++)
            ans[i][colEnd] = counter++;
        colEnd--;

        // bottom right to bottom left
        for(int i=colEnd; i>=colBegin; i--)
            ans[rowEnd][i] = counter++;
        rowEnd--;

        // bottom left to top left
        for(int i=rowEnd; i>=rowBegin; i--)
            ans[i][colBegin] = counter++;
        colBegin++;
    }
    return ans;
}
Enter fullscreen mode Exit fullscreen mode

Discussion (0)

pic
Editor guide