Spiral Matrix Ii

Solution For Spiral Matrix Ii

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

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

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

Approach:
To solve this problem, we can generate a matrix of size nn and fill it with zeros. After this, we can traverse the matrix in a spiral order and fill it with integers from 1 to nn. We can achieve this by keeping track of the four edges of the matrix, i.e., top, bottom, left, and right. We start by filling the top row, then the right column, then the bottom row, and then the left column. We continue this process until all the elements of the matrix are filled.

Algorithm:

  1. Create an empty n*n matrix filled with zeros
  2. Initialize counter = 1
  3. Initialize top, left, bottom, right pointers pointing to the first row, first column, last row, and last column of the matrix.
  4. Traverse the matrix in a spiral order by filling each element with counter. Increment the counter after filling each element.
    a. Fill the top row from left to right (i.e., from left pointer to right pointer).
    b. Increment the top pointer. If top pointer > bottom pointer, break the traversal.
    c. Fill the right column from top to bottom (i.e., from top pointer to bottom pointer).
    d. Decrement the right pointer. If left pointer > right pointer, break the traversal.
    e. Fill the bottom row from right to left (i.e., from right pointer to left pointer).
    f. Decrement the bottom pointer. If top pointer > bottom pointer, break the traversal.
    g. Fill the left column from bottom to top (i.e., from bottom pointer to top pointer).
    h. Increment the left pointer. If left pointer > right pointer, break the traversal.
  5. Return the matrix.

Code:

class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
# create an empty matrix filled with zeros
matrix = [[0 for i in range(n)] for j in range(n)]

    counter = 1
    top, left, bottom, right = 0, 0, n-1, n-1

    while True:
        # fill the top row
        for i in range(left, right+1):
            matrix[top][i] = counter
            counter += 1
        top += 1
        if top > bottom:
            break

        # fill the right column
        for i in range(top, bottom+1):
            matrix[i][right] = counter
            counter += 1
        right -= 1
        if left > right:
            break

        # fill the bottom row
        for i in range(right, left-1, -1):
            matrix[bottom][i] = counter
            counter += 1
        bottom -= 1
        if top > bottom:
            break

        # fill the left column
        for i in range(bottom, top-1, -1):
            matrix[i][left] = counter
            counter += 1
        left += 1
        if left > right:
            break

    return matrix

Time Complexity: O(n^2) as we traverse all n^2 elements in the matrix.

Space Complexity: O(n^2) as we create a matrix of size n*n.

Step by Step Implementation For Spiral Matrix Ii

public class Solution {
    public int[][] generateMatrix(int n) {
        int[][] res = new int[n][n];
        if (n <= 0) return res;
        int num = 1;
        int rowStart = 0;
        int rowEnd = n - 1;
        int colStart = 0;
        int colEnd = n - 1;
        while (rowStart <= rowEnd && colStart <= colEnd) {
            // go right
            for (int i = colStart; i <= colEnd; i++) {
                res[rowStart][i] = num++;
            }
            rowStart++;
            // go down
            for (int i = rowStart; i <= rowEnd; i++) {
                res[i][colEnd] = num++;
            }
            colEnd--;
            // go left
            for (int i = colEnd; i >= colStart; i--) {
                res[rowEnd][i] = num++;
            }
            rowEnd--;
            // go up
            for (int i = rowEnd; i >= rowStart; i--) {
                res[i][colStart] = num++;
            }
            colStart++;
        }
        return res;
    }
}
def generateMatrix(n):
    """
    :type n: int
    :rtype: List[List[int]]
    """
    
    # create an empty matrix
    matrix = []
    for i in range(n):
        matrix.append([0] * n)
        
    # define boundaries
    top = 0
    bottom = n - 1
    left = 0
    right = n - 1
    num = 1
    
    # fill in the matrix in a spiral pattern
    while left <= right and top <= bottom:
        for i in range(left, right + 1):
            matrix[top][i] = num
            num += 1
        for i in range(top + 1, bottom):
            matrix[i][right] = num
            num += 1
        for i in range(right, left - 1, -1):
            matrix[bottom][i] = num
            num += 1
        for i in range(bottom - 1, top, -1):
            matrix[i][left] = num
            num += 1
        left += 1
        right -= 1
        top += 1
        bottom -= 1
        
    return matrix
var generateMatrix = function(n) {
    // create an empty n-by-n matrix
    let matrix = [];
    for (let i = 0; i < n; i++) {
        matrix.push([]);
    }
    
    // define the four directions we can move in
    let directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    
    // starting position and direction
    let position = [0, 0];
    let direction = 0;
    
    // fill in the matrix in a spiral pattern
    for (let i = 1; i <= n * n; i++) {
        matrix[position[0]][position[1]] = i;
        
        // figure out next position
        let nextPosition = [position[0] + directions[direction][0], position[1] + directions[direction][1]];
        
        // if the next position is out of bounds or already filled, change direction
        if (nextPosition[0] < 0 || nextPosition[0] >= n || nextPosition[1] < 0 || nextPosition[1] >= n || matrix[nextPosition[0]][nextPosition[1]] !== 0) {
            direction = (direction + 1) % 4;
            nextPosition = [position[0] + directions[direction][0], position[1] + directions[direction][1]];
        }
        
        position = nextPosition;
    }
    
    return matrix;
};
class Solution {
public:
    vector> generateMatrix(int n) {
        // Create an n x n matrix
        vector> matrix(n, vector(n));
        // Initialize start row, start column, end row, end column
        int r1 = 0, c1 = 0, r2 = n - 1, c2 = n - 1;
        // Initialize counter
        int num = 1;
        // Loop while start row is less than or equal to end row and start column is less than or equal to end column
        while (r1 <= r2 && c1 <= c2) {
            // Loop from start column to end column
            for (int c = c1; c <= c2; c++) {
                // Set current element to counter
                matrix[r1][c] = num;
                // Increment counter
                num++;
            }
            // Increment start row
            r1++;
            // Loop from start row to end row
            for (int r = r1; r <= r2; r++) {
                // Set current element to counter
                matrix[r][c2] = num;
                // Increment counter
                num++;
            }
            // Decrement end column
            c2--;
            // Loop from end column to start column
            for (int c = c2; c >= c1; c--) {
                // Set current element to counter
                matrix[r2][c] = num;
                // Increment counter
                num++;
            }
            // Decrement end row
            r2--;
            // Loop from end row to start row
            for (int r = r2; r >= r1; r--) {
                // Set current element to counter
                matrix[r][c1] = num;
                // Increment counter
                num++;
            }
            // Increment start column
            c1++;
        }
        // Return matrix
        return matrix;
    }
};
public class Solution {
    public int[][] GenerateMatrix(int n) {
        // Create an empty spiral matrix 
        int[][] spiral = new int[n][n];
        
        // Initialize value to 1 
        int value = 1;
        
        // Find the starting row and column for the first element 
        int sr = 0, sc = 0;
        
        // Loop through the matrix until all elements are filled 
        while (sr < n && sc < n) {
            // Loop through the current row from left to right 
            for (int i = sc; i < n; i++) {
                // Insert the value into the current cell 
                spiral[sr][i] = value;
                
                // Increment value by 1 
                value++;
            }
            
            // Move to the next row down 
            sr++;
            
            // Loop through the current column from top to bottom 
            for (int i = sr; i < n; i++) {
                // Insert the value into the current cell 
                spiral[i][n-1] = value;
                
                // Increment value by 1 
                value++;
            }
            
            // Move to the next column to the left 
            n--;
            
            // Loop through the current row from right to left 
            if (sr < n) {
                for (int i = n-1; i >= sc; i--) {
                    // Insert the value into the current cell 
                    spiral[n-1][i] = value;
                    
                    // Increment value by 1 
                    value++;
                }
                
                // Move to the next row up 
                n--;
            }
            
            // Loop through the current column from bottom to top 
            if (sc < n) {
                for (int i = n-1; i >= sr; i--) {
                    // Insert the value into the current cell 
                    spiral[i][sc] = value;
                    
                    // Increment value by 1 
                    value++;
                }
                
                // Move to the next column to the right 
                sc++;
            }
        }
        
        // Return the completed spiral matrix 
        return spiral;
    }
}


Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]