Spiral Matrix II Leetcode Solution

Difficulty Level Medium
Frequently asked in Accenture Amazon Apple Facebook Google Microsoft Oracle Uber
meta tiktokViews 3970

Problem Statement

This question Spiral Matrix II is very similar to  Spiral Matrix 

Please try to attempt the above question to get a better idea before solving this problem.

In this question, we are asked to generate a matrix of size n*n having elements in spiral order, and only n is given as input.

Spiral Matrix II Leetcode Solution

Algorithm

If we observe clearly, we can notice that no matter what n is, the order of directions for spirality will always be

east->south->west->north->east->… and so on

Hence, we can use 4 pointers and traverse an empty/ predefined 2D vector as per the spiral directionality and store a number and increment the number by 1.

Use 4 pointers – l for left, r for right, t for top, and d for down;

Cases:

  1. direction is east:
    1. traverse all columns from left to right, in the top row
    2. store num and increment num each time
    3. increment top by 1
    4. change direction to the south
  2. direction is south
    1. traverse all rows from top to down, in the rightmost column
    2. store num and increment num each time
    3. decrease right by 1
    4. change direction to the west
  3. direction is west
    1. traverse all columns from right to left, in the down row
    2. store num and increment num each time
    3. decrease down by 1
    4. change direction to the west
  4. direction is north
    1. traverse all rows from down to the top, in the leftmost column
    2. store num and increment num each time
    3. increment left by 1
    4. change direction to the west

we can iterate this till left <= right and top <= down in a while loop

The picture below depicts the algorithm

Spiral Matrix II Leetcode Solution

 

Code

Note: Pointers are – l for left, r for right, t for top, d for down

C++ program for Spiral Matrix II Leetcode Solution

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        char dir = 'E';
        vector<vector<int>> spiralMatrix(n, vector<int>(n,0));
        int num=1;
        int l=0, t=0, r=n-1, d=n-1;
        while(l<=r && t<=d) {
            if(dir == 'E') {
                for(int i=l; i<=r; i++) {
                    spiralMatrix[t][i] = num++;
                }
                t++;
                dir='S';
            }
            else if(dir=='S') {
                for(int i=t; i<=d; i++) {
                    spiralMatrix[i][r] = num++;
                }
                r--;
                dir='W';
            }
            else if(dir=='W') {
                for(int i=r; i>=l; i--) {
                    spiralMatrix[d][i] = num++;
                }
                d--;
                dir='N';
            }
            else {
                for(int i=d; i>=t; i--) {
                    spiralMatrix[i][l] = num++;
                }
                l++;
                dir='E';
            }
        }
        return spiralMatrix;
    }
};

Java program for Spiral Matrix II Leetcode Solution

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] spiralMatrix = new int[n][n];
        int num=1;
        char dir='E';
        int l=0, t=0, r=n-1, d=n-1;
        while(l<=r && t<=d) {
            if(dir == 'E') {
                for(int i=l; i<=r; i++) {
                    spiralMatrix[t][i] = num++;
                }
                t++;
                dir='S';
            }
            else if(dir=='S') {
                for(int i=t; i<=d; i++) {
                    spiralMatrix[i][r] = num++;
                }
                r--;
                dir='W';
            }
            else if(dir=='W') {
                for(int i=r; i>=l; i--) {
                    spiralMatrix[d][i] = num++;
                }
                d--;
                dir='N';
            }
            else {
                for(int i=d; i>=t; i--) {
                    spiralMatrix[i][l] = num++;
                }
                l++;
                dir='E';
            }
        }
        return spiralMatrix;
    }
}

Complexity Analysis for Spiral Matrix II Leetcode Solution

Time Complexity:

Here, n is given input and we are iterating over the n*n matrix in spiral form. Hence, O(n^2)

Space Complexity:

We have used constant extra space for storing num, hence O(1)

Reference: https://en.wikipedia.org/wiki/Spiral

 

Translate »