59. Spiral Matrix II

Description of Problem

Given a positive integer n, generate an n x n matrix filled with elements from 1 to n^2 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]]

Constraints:

• 1 <= n <= 20

Solution

Tags: Divide and Conquer

Explanation

Seqentially filling-in matrix from top, right, bottom left. This process reduce the problem size and continue the above process again.

Example (3x3 matrix):

Top:

Right:

Bottom:

Left:

Code

impl Solution {
    pub fn generate_matrix(n: i32) -> Vec<Vec<i32>> {
        let mut n = n as usize;
        let mut matrix = vec![ vec![0; n]; n];
        let mut counter = 1;
        let (mut row, mut col) = (0, 0);

        while n > 0 {
            println!("Loop: {n}");
            if n == 1 {
                matrix[row][col] = counter;
                counter+=1; n-=1;
            } else if n > 1 {
                Solution::fill1(&mut matrix, &mut counter, row, col, n);
                Solution::fill2(&mut matrix, &mut counter, row, col, n);
                Solution::fill3(&mut matrix, &mut counter, row, col, n);
                Solution::fill4(&mut matrix, &mut counter, row, col, n);
                row+=1; col+=1; n-=2;
            }
        }

        return matrix;
    }

    fn fill1(
        matrix : &mut Vec<Vec<i32>>, 
        counter: &mut i32, 
        row: usize, 
        col: usize, 
        n: usize
    ) {
        for j in 0..=(n-2) {
            matrix[row][col+j] = *counter;
            *counter +=1
        }
    }

    fn fill2(
        matrix : &mut Vec<Vec<i32>>, 
        counter: &mut i32, 
        row: usize, 
        col: usize, 
        n: usize
    ) {
        for i in 0..=(n-2) {
            matrix[row+i][col+n-1] = *counter;
            *counter +=1
        }
    }

    fn fill3(
        matrix : &mut Vec<Vec<i32>>, 
        counter: &mut i32, 
        row: usize, 
        col: usize, 
        n: usize
    ) {
        for j in (1..=(n-1)).rev() {
            matrix[row + n -1][col+j] = *counter;
            *counter +=1
        }
    }

    fn fill4(
        matrix : &mut Vec<Vec<i32>>, 
        counter: &mut i32, 
        row: usize, 
        col: usize, 
        n: usize
    ) {
        for i in (1..=(n-1)).rev() {
            matrix[row + i][col] = *counter;
            *counter +=1
        }
    }
}