Spiral Number Pattern
Problem
Read n and print an n by n square filled with the numbers 1 to n*n in a clockwise spiral. Start at the top-left corner and go right first. Separate the numbers in a row with one space.
Constraints
- 1 <= n <= 20
Examples
Input
3
Output
1 2 3 8 9 4 7 6 5
Solutions
We keep four borders. We fill the top row, right column, bottom row, and left column one after the other, and move each border one step inward after it is used. The two if checks stop the loop from writing a row or column twice when the area becomes a single row or column.
Java 8 has no String.repeat, so we use a small helper method. In Java 11 and newer you can write " ".repeat(count).
/*
* Problem : Spiral square.
* Input : One integer n (side length).
* Output : n lines of n numbers.
* Approach: Walk around the borders and move the borders inward.
* Time : O(n^2)
* Space : O(n^2)
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
int size = new Scanner(System.in).nextInt();
int[][] grid = new int[size][size];
// Step 1: Set the four borders of the area that is still empty.
int top = 0;
int bottom = size - 1;
int left = 0;
int right = size - 1;
// Step 2: The next number to write. It starts at 1.
int value = 1;
// Step 3: Repeat while the empty area still has rows and columns.
while (top <= bottom && left <= right) {
// Step 3a: Go right along the top row, then move the top border down.
for (int column = left; column <= right; column++) {
grid[top][column] = value++;
}
top++;
// Step 3b: Go down along the right column, then move the right border left.
for (int row = top; row <= bottom; row++) {
grid[row][right] = value++;
}
right--;
// Step 3c: Go left along the bottom row, if a row is left. Then move the bottom border up.
if (top <= bottom) {
for (int column = right; column >= left; column--) {
grid[bottom][column] = value++;
}
bottom--;
}
// Step 3d: Go up along the left column, if a column is left. Then move the left border right.
if (left <= right) {
for (int row = bottom; row >= top; row--) {
grid[row][left] = value++;
}
left++;
}
}
// Step 4: Print every row of the grid with one space between numbers.
for (int row = 0; row < size; row++) {
StringBuilder line = new StringBuilder();
for (int column = 0; column < size; column++) {
if (column > 0) {
line.append(" ");
}
line.append(grid[row][column]);
}
System.out.println(line);
}
}
}
Hints (3)
- Fill one side at a time: right, down, left, up.
- After each side, make the empty area smaller.
- What happens when only one row or column is left?