Problem Statement

Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

Example:

Input: 3
Output:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

Solution Explanation

This problem is similar to Spiral Matrix Leetcode problem. To solve this problem, first we need to know, how spiral order works. The way spiral order work is that it follow four directions: First, it goes right. Second, it goes down. Third, it goes left and Fourth, it goes up. We are literally going to just follow these four directions order by first initializing matrix n*n and keep adding elements from 1 till we have reached our row and columns limit in matrix. Read the comments provided in below solution code to understand further more.

class Solution {
    public int[][] generateMatrix(int n) {
        
        //Matrix initialization
        int[][] matrix = new int[n][n];
        
        //Initialized rowBegin,rowEnd,colBegin and ColEnd
        int rowBegin = 0, rowEnd = n-1,colBegin = 0, colEnd = n-1;
        
        //Element initialization which we going to add in matrix from 1 to n^2
        int k = 1;
        
        while(rowBegin <= rowEnd && colBegin <= colEnd){
            
            //Traverse right, add elements and increment rowBegin
            for(int i = colBegin; i <= colEnd; i++){
                matrix[rowBegin][i] = k++;
            }
            rowBegin++;
            
            //Traverse down, add elements and decrement colEnd
            for(int i = rowBegin; i <= rowEnd; i++){
                matrix[i][colEnd] = k++;
            }
            colEnd--;
            
             //The only tricky part here is when we traverse left or up, we have to make sure that we have not visited those row and columns already. 
            
            //Make sure that row has not been visited 
            //Traverse left, add elements and decrement rowEnd
            if(rowBegin <= rowEnd){
                for(int i = colEnd; i >= colBegin; i--){
                    matrix[rowEnd][i] = k++;
                }
            }
            rowEnd--;
            
             //Make sure that column has not been visited 
            //Traverse up, add elements and increment colBegin
            if(colBegin <= colEnd){
                for(int i = rowEnd; i>= rowBegin; i--){
                    matrix[i][colBegin] = k++;
                }
            }
            colBegin++;
            
        }
        
        return matrix;
    }
}

Time Complexity

We are going to visit each indexes in matrix to add elements so time complexity is going to be: O(n*n).

Space Complexity

We are creating n*n matrix and adding elements into matrix, so space complexity is going to be: O(n*n).