59. Spiral Matrix II

Published on June 3, 2023

Question

Given a positive integer n, generate an n x n 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]]

Algorithm

This question is much similar to the previous one Spiral Matrix. You need to construct a board and traverse in a spiral order and fill out each blank with a increasing number until all the number are used(or the 2-D array is full).

At each step, you need to care about if the top/bottom or left/right boundary is in a valid relative position. By this I mean, we are modifying those boundaries, we need to keep top is less or equal to the bottom to avoid the number goes back and overlapping.

Code

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