☕ DSA Java Articles

Topics › Basics › Patterns

Pattern 12

Easy TUF ID 404 A2Z

Java source ↗ Edit this article ↗

Problem

Given a positive integer n, print the number crown: n rows, each 2n characters wide. Row i (counting from 1) prints the numbers 1, 2, ..., i on the left, the numbers i, ..., 2, 1 on the right, and fills the middle with spaces so that the two halves move towards each other and finally meet in the last row.

Constraints: 1 ≤ n ≤ 9 in the classic version, so that every number is a single character and the rows stay aligned. The code below also works for larger n, but the picture skews once two-digit numbers appear.

Example 1

n = 3
1    1
12  21
123321

Row 1 has one number on each side and four spaces between; row 3 has no spaces left.

Example 2

n = 5
1        1
12      21
123    321
1234  4321
1234554321

Each row is 10 characters wide; the gap shrinks by two characters per row.

Reading the pattern

Every printing pattern becomes easy once you can describe one row with a formula in i and n. Look at the anatomy of a row here: three parts, left to right.

part content length
left half 1 2 ... i i
gap spaces 2(n - i)
right half i ... 2 1 i

The three lengths add up to i + 2(n - i) + i = 2n, which is why every row has the same width. The gap starts at 2(n - 1) in row 1 and shrinks by exactly two per row, because each new row adds one character on the left and one on the right. That “shrinks by two” is the detail people get wrong most often; n - i spaces would give a lopsided crown.

For n = 5 the parts are:

i left gap right
1 1 8 1
2 12 6 21
3 123 4 321
4 1234 2 4321
5 12345 0 54321

Both approaches below return the finished picture as a single String (rows separated by \n) instead of printing directly. That makes the result testable: main compares the string against hand-written expectations and only then prints it.

Approach 1: Three loops per row

Intuition. Translate the row anatomy literally. An outer loop walks the rows; inside it, one loop prints the ascending numbers, one prints the spaces, one prints the descending numbers. Nothing is remembered between rows, so every row is computed from scratch using only i and n.

Algorithm.

  1. For i from 1 to n:
  2. Append j for j = 1 .. i.
  3. Append 2(n - i) spaces.
  4. Append j for j = i .. 1.
  5. End the row with a newline.
static String nestedLoops(int n) {
    StringBuilder sb = new StringBuilder();
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) sb.append(j);          // 1 2 ... i
        for (int j = 0; j < 2 * (n - i); j++) sb.append(' '); // shrinking gap
        for (int j = i; j >= 1; j--) sb.append(j);          // i ... 2 1
        sb.append('\n');
    }
    return sb.toString();
}

Complexity. Time O(n^2): n rows of 2n characters each, and every character costs O(1) to append. Space O(n^2) for the returned string, which is unavoidable because that is the size of the output; no extra working memory beyond the builder.

Note that sb.append(j) with an int argument appends the decimal text of j ("12" for twelve). sb.append((char) j) would append the character with code point j, an invisible control character, which is a classic mix-up.

Approach 2: Grow the two halves incrementally

Intuition. The left half of row i is the left half of row i - 1 with i appended. The right half of row i is the right half of row i - 1 with i prepended. So instead of rebuilding both halves from 1 each time, keep them in two StringBuilders that grow by one number per row, and glue left + gap + right together. The gap is a single call to " ".repeat(2 * (n - i)).

This is the same work asymptotically, but it changes the way you think: a row is “the previous row, slightly extended”, a viewpoint that pays off in harder patterns where recomputation is expensive.

Algorithm.

  1. Keep left = "" and right = "".
  2. For i from 1 to n: append i to left, insert i at position 0 of right.
  3. Append left, then 2(n - i) spaces, then right, then a newline.
static String incremental(int n) {
    StringBuilder sb = new StringBuilder();
    StringBuilder left = new StringBuilder();   // "12...i"
    StringBuilder right = new StringBuilder();  // "i...21"
    for (int i = 1; i <= n; i++) {
        left.append(i);
        right.insert(0, i);
        sb.append(left).append(" ".repeat(2 * (n - i))).append(right).append('\n');
    }
    return sb.toString();
}

Dry run for n = 4:

i left gap right row
1 1 6 1 1 1
2 12 4 21 12 21
3 123 2 321 123 321
4 1234 0 4321 12344321

Complexity. Time O(n^2). insert(0, i) shifts the existing characters, so it costs O(i), and copying left and right into the output also costs O(i) per row; summed over the rows that is O(n^2), the same as the output size. Space O(n^2) for the output plus O(n) for the two halves.

Why does prepending give the reverse order for free? Because the sequence i, i-1, ..., 1 is exactly what you get when each new number lands in front of the earlier ones. For two-digit numbers this is also more robust than reversing a string: reversing "...910" would produce "019...", while prepending 10 keeps it intact.

Edge cases and pitfalls