Spiral Matrix II

Leetcode Daily Challenge (10th May, 2023)

10 May, 2023

Contributors

Lakshit Chiranjiv Sagar

@lakshit-cs

Problem Statement:-

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

Link: https://leetcode.com/problems/spiral-matrix-ii/description/

Problem Explanation with examples:-

Example 1

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

Example 2

Input: n = 1
Output: [[1]]

Constraints

1 <= n <= 20

Intuition:-

There will be a matrix that will contain the indices of the elements in the spiral order.
We can use the spiralOrder function from the previous problem to get the indices of the elements in the spiral order.
We can use the indices from the spiralOrder function to fill the matrix with the numbers from 1 to n*n using a for loop and enumerate function.

Solution:-

Initialize a variable ans to a matrix of size n*n with all elements as 0.
Initialize a variable mat to a matrix of size n*n with all elements as tuples of the form (i,j) where i and j are the row and column indices respectively.
Define a spiralOrder function which takes a matrix as a parameter and returns the elements of the matrix in spiral order as a list by popping the first row and calling the spiralOrder function on the transpose of the matrix.
Call the spiralOrder function with mat as a parameter and store the result in a variable order.
For each index ind and value v in order, set the element at the indices v[0] and v[1] in ans to ind+1.
Return ans.

Code:-

JAVA Solution

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] ans = new int[n][n];
        int[][] mat = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                mat[i][j] = i * n + j;
            }
        }

        List<Integer> order = spiralOrder(mat);

        for (int i = 0; i < order.size(); i++) {
            int row = order.get(i) / n;
            int col = order.get(i) % n;
            ans[row][col] = i + 1;
        }

        return ans;
    }

    private List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        if (matrix == null || matrix.length == 0) {
            return res;
        }
        int m = matrix.length, n = matrix[0].length;
        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        boolean[][] visited = new boolean[m][n];
        int i = 0, j = 0, k = 0;
        for (int p = 0; p < m * n; p++) {
            res.add(matrix[i][j]);
            visited[i][j] = true;
            int nexti = i + dirs[k][0], nextj = j + dirs[k][1];
            if (nexti < 0 || nexti >= m || nextj < 0 || nextj >= n || visited[nexti][nextj]) {
                k = (k + 1) % 4;
                nexti = i + dirs[k][0];
                nextj = j + dirs[k][1];
            }
            i = nexti;
            j = nextj;
        }
        return res;
    }
}

Python Solution

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        ans = [[0]*n for k in range(n)]
        mat = [[tuple([i, j]) for j in range(n)] for i in range(n)]

        def spiralOrder(matrix):
            return matrix and list(matrix.pop(0)) + spiralOrder(list(zip(*matrix))[::-1])
        
        order = spiralOrder(mat)
        
        for ind, v in enumerate(order):
            ans[v[0]][v[1]] = ind+1
            
        return ans

Complexity Analysis:-

TIME:-

The time complexity is O(n^2) because it needs to fill the entire matrix with values from 1 to n^2.

SPACE:-

The space complexity is O(n^2) because it needs to create two matrices, one to store the answer and one to store the coordinates of each cell.

References:-

Recursion

Connect with me:-

java

python

leetcode

dsa