Spiral Matrix Ii

                                            
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> matrix(n, vector<int>(n, 0));
        int top = 0, bottom = n - 1, left = 0, right = n - 1;
        int num = 1;

        while (num <= n * n) {
            for (int i = left; i <= right; i++) {
                matrix[top][i] = num++;
            }
            top++;

            for (int i = top; i <= bottom; i++) {
                matrix[i][right] = num++;
            }
            right--;

            for (int i = right; i >= left; i--) {
                matrix[bottom][i] = num++;
            }
            bottom--;

            for (int i = bottom; i >= top; i--) {
                matrix[i][left] = num++;
            }
            left++;
        }

        return matrix;
    }
};

                                            
class Solution {
    public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        int num = 1;
        int top = 0, bottom = n - 1, left = 0, right = n - 1;
        
        while(num <= n*n) {
            for(int i = left; i <= right; i++) {
                matrix[top][i] = num++;
            }
            top++;
            
            for(int i = top; i <= bottom; i++) {
                matrix[i][right] = num++;
            }
            right--;
            
            for(int i = right; i >= left; i--) {
                matrix[bottom][i] = num++;
            }
            bottom--;
            
            for(int i = bottom; i >= top; i--) {
                matrix[i][left] = num++;
            }
            left++;
        }
        
        return matrix;
    }
}

                                            
class Solution(object):
    def generateMatrix(self, n):
        matrix = [[0 for _ in range(n)] for _ in range(n)]
        top, bottom, left, right = 0, n - 1, 0, n - 1
        num = 1
        
        while num <= n * n:
            for i in range(left, right + 1):
                matrix[top][i] = num
                num += 1
            top += 1
            
            for i in range(top, bottom + 1):
                matrix[i][right] = num
                num += 1
            right -= 1
            
            for i in range(right, left - 1, -1):
                matrix[bottom][i] = num
                num += 1
            bottom -= 1
            
            for i in range(bottom, top - 1, -1):
                matrix[i][left] = num
                num += 1
            left += 1
        
        return matrix

                                            
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, 
assume caller calls free().
 */
int** generateMatrix(int n, int* returnSize, int** returnColumnSizes) {
    int i, k = 1;
    int **matrix = (int**)malloc(sizeof(int*) * n);
    for (i = 0; i < n; i++) {
        matrix[i] = (int*)malloc(sizeof(int) * n);
    }

    int top = 0, bottom = n - 1, left = 0, right = n - 1;
    
    while (k <= n * n) {
        for (i = left; i <= right; i++) {
            matrix[top][i] = k++;
        }
        top++;
        
        for (i = top; i <= bottom; i++) {
            matrix[i][right] = k++;
        }
        right--;
        
        for (i = right; i >= left; i--) {
            matrix[bottom][i] = k++;
        }
        bottom--;
        
        for (i = bottom; i >= top; i--) {
            matrix[i][left] = k++;
        }
        left++;
    }
    
    *returnSize = n;
    *returnColumnSizes = (int*)malloc(sizeof(int) * n);
    for (i = 0; i < n; i++) {
        (*returnColumnSizes)[i] = n;
    }
    
    return matrix;
}

                                            
public class Solution {
    public int[][] GenerateMatrix(int n) {
        int[][] matrix = new int[n][];
        for (int i = 0; i < n; i++) {
            matrix[i] = new int[n];
        }
        
        int top = 0, bottom = n - 1, left = 0, right = n - 1;
        int num = 1;
        
        while (num <= n * n) {
            for (int i = left; i <= right; i++) {
                matrix[top][i] = num++;
            }
            top++;
            
            for (int i = top; i <= bottom; i++) {
                matrix[i][right] = num++;
            }
            right--;
            
            for (int i = right; i >= left; i--) {
                matrix[bottom][i] = num++;
            }
            bottom--;
            
            for (int i = bottom; i >= top; i--) {
                matrix[i][left] = num++;
            }
            left++;
        }
        
        return matrix;
    }
}

                                            
function generateMatrix(n: number): number[][] {
    const matrix: number[][] = new Array(n).fill(0).map(() => new Array(n).fill(0));
    
    let num = 1;
    let top = 0, bottom = n - 1, left = 0, right = n - 1;
    
    while(num <= n * n) {
        for(let i = left; i <= right; i++) {
            matrix[top][i] = num++;
        }
        top++;
        
        for(let i = top; i <= bottom; i++) {
            matrix[i][right] = num++;
        }
        right--;
        
        for(let i = right; i >= left; i--) {
            matrix[bottom][i] = num++;
        }
        bottom--;
        
        for(let i = bottom; i >= top; i--) {
            matrix[i][left] = num++;
        }
        left++;
    }
    
    return matrix;
};

                                            
class Solution {
    /**
     * @param Integer $n
     * @return Integer[][]
     */
    function generateMatrix($n) {
        $matrix = array_fill(0, $n, array_fill(0, $n, 0));
        $top = 0;
        $bottom = $n - 1;
        $left = 0;
        $right = $n - 1;
        $num = 1;
        
        while ($num <= $n * $n) {
            for ($i = $left; $i <= $right; $i++) {
                $matrix[$top][$i] = $num++;
            }
            $top++;
            
            for ($i = $top; $i <= $bottom; $i++) {
                $matrix[$i][$right] = $num++;
            }
            $right--;
            
            for ($i = $right; $i >= $left; $i--) {
                $matrix[$bottom][$i] = $num++;
            }
            $bottom--;
            
            for ($i = $bottom; $i >= $top; $i--) {
                $matrix[$i][$left] = $num++;
            }
            $left++;
        }
        
        return $matrix;
    }
}

                                            
class Solution {
    func generateMatrix(_ n: Int) -> [[Int]] {
        var result = Array(repeating: Array(repeating: 0, count: n), count: n)
        var top = 0, bottom = n - 1, left = 0, right = n - 1
        var num = 1

        while num <= n * n {
            for i in stride(from: left, through: right, by: 1) {
                result[top][i] = num
                num += 1
            }
            top += 1

            for i in stride(from: top, through: bottom, by: 1) {
                result[i][right] = num
                num += 1
            }
            right -= 1

            for i in stride(from: right, through: left, by: -1) {
                result[bottom][i] = num
                num += 1
            }
            bottom -= 1

            for i in stride(from: bottom, through: top, by: -1) {
                result[i][left] = num
                num += 1
            }
            left += 1
        }

        return result
    }
}

                                            
class Solution {
    fun generateMatrix(n: Int): Array<IntArray> {
        val matrix = Array(n) { IntArray(n) }
        var num = 1
        var top = 0
        var bottom = n - 1
        var left = 0
        var right = n - 1

        while (num <= n * n) {
            for (i in left..right) {
                matrix[top][i] = num++
            }
            top++
            for (i in top..bottom) {
                matrix[i][right] = num++
            }
            right--
            for (i in right downTo left) {
                matrix[bottom][i] = num++
            }
            bottom--
            for (i in bottom downTo top) {
                matrix[i][left] = num++
            }
            left++
        }

        return matrix
    }
}

                                            
class Solution {
  List<List<int>> generateMatrix(int n) {
    List<List<int>> matrix = List.generate(n, (_) => List.filled(n, 0));
    
    int top = 0, bottom = n - 1, left = 0, right = n - 1;
    int num = 1;
    
    while (num <= n * n) {
      for (int i = left; i <= right; i++) {
        matrix[top][i] = num++;
      }
      top++;
      
      for (int i = top; i <= bottom; i++) {
        matrix[i][right] = num++;
      }
      right--;
      
      for (int i = right; i >= left; i--) {
        matrix[bottom][i] = num++;
      }
      bottom--;
      
      for (int i = bottom; i >= top; i--) {
        matrix[i][left] = num++;
      }
      left++;
    }
    
    return matrix;
  }
}

                                            
func generateMatrix(n int) [][]int {
    matrix := make([][]int, n)
    for i := range matrix {
        matrix[i] = make([]int, n)
    }

    num := 1
    top, bottom, left, right := 0, n-1, 0, n-1

    for num <= n*n {
        for i := left; i <= right; i++ {
            matrix[top][i] = num
            num++
        }
        top++

        for i := top; i <= bottom; i++ {
            matrix[i][right] = num
            num++
        }
        right--

        for i := right; i >= left; i-- {
            matrix[bottom][i] = num
            num++
        }
        bottom--

        for i := bottom; i >= top; i-- {
            matrix[i][left] = num
            num++
        }
        left++
    }

    return matrix
}

                                            
# @param {Integer} n
# @return {Integer[][]}
def generate_matrix(n)
    matrix = Array.new(n) { Array.new(n, 0) }
    top = 0
    bottom = n - 1
    left = 0
    right = n - 1
    num = 1

    while top <= bottom && left <= right
        left.upto(right) do |i|
            matrix[top][i] = num
            num += 1
        end
        top += 1

        top.upto(bottom) do |i|
            matrix[i][right] = num
            num += 1
        end
        right -= 1

        if top <= bottom
            right.downto(left) do |i|
                matrix[bottom][i] = num
                num += 1
            end
            bottom -= 1
        end

        if left <= right
            bottom.downto(top) do |i|
                matrix[i][left] = num
                num += 1
            end
            left += 1
        end
    end

    matrix
end

                                            
object Solution {
    def generateMatrix(n: Int): Array[Array[Int]] = {
        val matrix = Array.ofDim[Int](n, n)
        var top = 0
        var bottom = n - 1
        var left = 0
        var right = n - 1
        var num = 1

        while (num <= n * n) {
            for (i <- left to right) {
                matrix(top)(i) = num
                num += 1
            }
            top += 1

            for (i <- top to bottom) {
                matrix(i)(right) = num
                num += 1
            }
            right -= 1

            for (i <- right to left by -1) {
                matrix(bottom)(i) = num
                num += 1
            }
            bottom -= 1

            for (i <- bottom to top by -1) {
                matrix(i)(left) = num
                num += 1
            }
            left += 1
        }

        matrix
    }
}

                                            
impl Solution {
    pub fn generate_matrix(n: i32) -> Vec<Vec<i32>> {
        let mut matrix = vec![vec![0; n as usize]; n as usize];
        let (mut top, mut bottom, mut left, mut right) = (0, n as usize - 1, 0, n as usize - 1);
        let mut num = 1;

        while num <= n * n {
            for i in left..=right {
                matrix[top][i] = num;
                num += 1;
            }
            top += 1;

            for i in top..=bottom {
                matrix[i][right] = num;
                num += 1;
            }
            right -= 1;

            if top <= bottom {
                for i in (left..=right).rev() {
                    matrix[bottom][i] = num;
                    num += 1;
                }
                bottom -= 1;
            }

            if left <= right {
                for i in (top..=bottom).rev() {
                    matrix[i][left] = num;
                    num += 1;
                }
                left += 1;
            }
        }

        matrix
    }
}

To solve this coding challenge, we need to generate an \( n \times n \) matrix filled with elements from 1 to \( n \times n \) in a spiral order. This requires filling the matrix in layers, starting from the outermost layer and moving inward. We will keep track of our boundaries and fill elements by moving right, down, left, and up within those boundaries.

Explanation

Initialize the Matrix : We'll start by initializing an \( n \times n \) matrix with all elements set to zero.
Initialize Boundary Pointers : Four pointers will help us control the boundaries while iterating over the matrix. These are top, bottom, left, and right.
Filling the Matrix : Using a while-loop, fill the matrix elements in four directions — from left to right, top to bottom, right to left, and bottom to top. Adjust the boundaries after filling in each direction.
Loop Termination : The loop will terminate when the current number exceeds \( n \times n \).
Return Result : Finally, return the filled matrix.

Step-by-Step Explanation

Initialization

Matrix Initialization :

Create an \( n \times n \) matrix with all zeros.

Boundary Pointers :

top pointer starts at 0.
bottom pointer starts at \( n-1 \).
left pointer starts at 0.
right pointer starts at \( n-1 \).

Element to be Filled :

Start filling with the number 1.

While Loop

Move Right :

From left to right within the top boundary, fill elements. Increment the top boundary afterward.

Move Down :

From top to bottom within the right boundary, fill elements. Decrement the right boundary afterward.

Move Left :

From right to left within the bottom boundary, fill elements. Decrement the bottom boundary afterward.

Move Up :

From bottom to top within the left boundary, fill elements. Increment the left boundary afterward.

Conditions

Continue the loop until the number to be filled exceeds \( n \times n \).

Detailed Steps in Pseudocode

                                            
# Initialize the matrix to be filled with zeros
matrix = create_empty_matrix(n, n)

# Initialize the boundary pointers
top = 0
bottom = n - 1
left = 0
right = n - 1

# Start with the number 1
num = 1

# Fill the matrix while num is less than or equal to n*n
while num <= n * n:
    # Fill from left to right within the top boundary
    for i from left to right inclusive:
        matrix[top][i] = num
        num += 1
    # Move the top boundary downward
    top += 1
    
    # Fill from top to bottom within the right boundary
    for i from top to bottom inclusive:
        matrix[i][right] = num
        num += 1
    # Move the right boundary leftward
    right -= 1
    
    # Fill from right to left within the bottom boundary
    for i from right to left inclusive:
        matrix[bottom][i] = num
        num += 1
    # Move the bottom boundary upward
    bottom -= 1
    
    # Fill from bottom to top within the left boundary
    for i from bottom to top inclusive:
        matrix[i][left] = num
        num += 1
    # Move the left boundary rightward
    left += 1

# Return the filled matrix
return matrix

Comments in Pseudocode for Clarity

                                            
# Create an empty n x n matrix
matrix = [[0 for each column in range(n)] for each row in range(n)]

# Initialize boundaries
top = 0
bottom = n - 1
left = 0
right = n - 1

# Starting number
num = 1

# Perform the spiral filling
while num <= n * n:
    # Fill the top row from the left boundary to the right boundary
    for i in range(left to right inclusive):
        matrix[top][i] = num
        num += 1
    # Move the top boundary down 
    top += 1
    
    # Fill the right column from the top boundary to the bottom boundary
    for i in range(top to bottom inclusive):
        matrix[i][right] = num
        num += 1
    # Move the right boundary left 
    right -= 1
    
    # Fill the bottom row from the right boundary to the left boundary
    for i in range(right to left inclusive):
        matrix[bottom][i] = num
        num += 1
    # Move the bottom boundary up 
    bottom -= 1
    
    # Fill the left column from the bottom boundary to the top boundary
    for i in range(bottom to top inclusive):
        matrix[i][left] = num
        num += 1
    # Move the left boundary right 
    left += 1

# Return the filled matrix
return matrix

By the end of this exhaustive explanation and pseudocode, you'll be able to implement and understand the methodology for generating a spiral matrix effectively.