Zig-Zag Number Pattern

easy Pattern Printing

Problem

Read n and print an n by n grid with the numbers 1 to n*n. Odd rows (1st, 3rd, ...) go from left to right. Even rows (2nd, 4th, ...) go from right to left, so the numbers move like a snake.

Constraints

  • 1 <= n <= 20

Examples

Input

3

Output

1 2 3
6 5 4
7 8 9

Solutions

Best approachTime O(n^2)Space O(1)

Every row holds n consecutive numbers. On even-numbered rows (counting from 0) we write them from left to right, on odd-numbered rows from right to left. The remainder operator (%) tells us if the row number is even or odd.

Same code works in Java810172125Basic features only, so nothing changes between versions.

Java 8 has no String.repeat, so we use a small helper method. In Java 11 and newer you can write " ".repeat(count).

/*
 * Problem : Snake (zig-zag) grid.
 * Input   : One integer n (side length).
 * Output  : n lines of n numbers.
 * Approach: Reverse every second row.
 * Time    : O(n^2)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        int size = new Scanner(System.in).nextInt();

        // Step 1: Repeat once for each row. Row numbers start at 0.
        for (int row = 0; row < size; row++) {
            // Step 2: Find the first number of this row. Example: size 4 -> row 1 starts at 5.
            int first = row * size + 1;
            StringBuilder line = new StringBuilder();

            // Step 3: Visit the columns of the row.
            for (int column = 0; column < size; column++) {
                // Step 4: Rows 0, 2, 4 go from left to right. Rows 1, 3, 5 go from right to left.
                int number = (row % 2 == 0) ? first + column : first + size - 1 - column;

                if (column > 0) {
                    line.append(" ");
                }
                line.append(number);
            }

            // Step 5: Print the finished line.
            System.out.println(line);
        }
    }
}
Hints (2)
  1. Each row is a block of n consecutive numbers.
  2. Which rows are reversed? Use row % 2.