Topics › Basics › Patterns

Pattern 9

Easy TUF ID 422 A2Z

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

Given an integer n, print a diamond made of stars: an upright centred pyramid of n rows (widths 1, 3, ..., 2n - 1) immediately followed by an inverted centred pyramid of n rows (widths 2n - 1, ..., 3, 1). The diamond therefore has 2n rows, and the two middle rows are both 2n - 1 stars wide.

Output format: every row ends with a newline and there are no trailing spaces. n = 0 prints nothing.

Constraints: 0 ≤ n ≤ 100 is typical.

Example 1

n = 3

  *
 ***
*****
*****
 ***
  *

Rows 1 to 3 widen, rows 4 to 6 narrow; the two full rows in the middle are the signature of this variant.

Example 2

n = 1

*
*

The two single-row pyramids simply stack.

Composition, then compression

This is the first pattern that is naturally two patterns. The upper half is the star pyramid: row i (0-based) has n - 1 - i spaces and 2i + 1 stars. The lower half is the inverted pyramid: row i has i spaces and 2(n - i) - 1 stars. Printing one after the other is a complete solution and is how you should first solve it.

The deeper lesson is what comes after: once both halves are written, you notice the lower half is the upper half read backwards, and then that both halves are governed by a single quantity, the distance from the nearer tip. Each approach below is one step along that path.

All approaches return the pattern as a String so the tests can compare it with expected literals.

Approach 1: Two blocks of nested loops

Intuition. Write the upright pyramid loops, then the inverted pyramid loops, into the same builder. Each half has its own space and star formulas.

Algorithm.

1. For i from 0 to n - 1: append n - 1 - i spaces, 2i + 1 stars, \n.
2. For i from 0 to n - 1: append i spaces, 2(n - i) - 1 stars, \n.
3. Return the string.

static String nestedLoops(int n) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < n; i++) {                    // upper half: row i has 2i+1 stars
        for (int j = 0; j < n - 1 - i; j++) sb.append(' ');
        for (int j = 0; j < 2 * i + 1; j++) sb.append('*');
        sb.append('\n');
    }
    for (int i = 0; i < n; i++) {                    // lower half: row i has 2(n-i)-1 stars
        for (int j = 0; j < i; j++) sb.append(' ');
        for (int j = 0; j < 2 * (n - i) - 1; j++) sb.append('*');
        sb.append('\n');
    }
    return sb.toString();
}

Complexity. Time O(n^2): about 1.5 n^2 characters per half. Space O(n^2) for the output, O(1) extra.

Approach 2: Build the upper half, then mirror it

Intuition. Row r of the lower half equals row n - 1 - r of the upper half; the whole diamond is vertically symmetric. So compute the upper rows once into a list, emit the list forwards, then emit it backwards. There is only one set of formulas to get right, and the symmetry is enforced by construction rather than by matching two sets of loops. The tests check this symmetry explicitly: rows[r] must equal rows[2n - 1 - r] for every r.

Algorithm.

1. For i from 0 to n - 1, add " ".repeat(n - 1 - i) + "*".repeat(2i + 1) to upper.
2. Append every row of upper followed by \n.
3. Append upper from index n - 1 down to 0, each followed by \n.

static String mirror(int n) {
    List<String> upper = new ArrayList<>();
    for (int i = 0; i < n; i++) upper.add(" ".repeat(n - 1 - i) + "*".repeat(2 * i + 1));
    StringBuilder out = new StringBuilder();
    for (String row : upper) out.append(row).append('\n');
    for (int i = n - 1; i >= 0; i--) out.append(upper.get(i)).append('\n');
    return out.toString();
}

Complexity. Time O(n^2), space O(n^2) for the stored half, plus the output.

Approach 3: A single loop with a folded index

Intuition. Number the 2n rows r = 0 .. 2n - 1 and ask: how far is row r from the nearer tip of the diamond? For the upper half that is k = r; for the lower half it is k = 2n - 1 - r (row 2n - 1 is distance 0 from the bottom tip). Every row then has n - 1 - k spaces and 2k + 1 stars, the same formula as the upright pyramid. The two halves collapse into one loop and one pair of formulas; only the index is “folded” at the middle.

Folding the index like this is a general trick for symmetric sequences, and it is the same idea used for the half diamond, where the star count is min(i, 2n - i).

Algorithm.

1. For r from 0 to 2n - 1: k = r < n ? r : 2n - 1 - r.
2. Append n - 1 - k spaces, 2k + 1 stars, \n.

static String foldedIndex(int n) {
    StringBuilder out = new StringBuilder();
    for (int r = 0; r < 2 * n; r++) {
        int k = r < n ? r : 2 * n - 1 - r;           // distance from the nearer tip
        out.append(" ".repeat(n - 1 - k)).append("*".repeat(2 * k + 1)).append('\n');
    }
    return out.toString();
}

Dry run for n = 3:

Rows 2 and 3 both map to k = 2, which is exactly why the middle row is doubled.

Complexity. Time O(n^2), space O(n) extra for the row pieces.

Edge cases and pitfalls

• n = 0. Returns ""; 2n = 0 rows.
• n = 1. "*\n*\n": two single stars, because each half contributes one row.
• Doubled middle row. This pattern intentionally has 2n rows with two equal rows in the middle. A diamond with a single widest row has 2n - 1 rows and uses k = r < n ? r : 2n - 2 - r; be sure which one is asked.
• Trailing spaces. Printing symmetric spaces on the right looks identical but fails exact comparison. This article omits them.
• Mixing the two halves’ formulas. In the two-block version it is easy to copy n - 1 - i spaces into the lower half. Plug in the first row of each half to check: the lower half must start with 0 spaces and 2n - 1 stars.
• Negative repeat count. If k is computed wrongly (for example 2n - r instead of 2n - 1 - r), n - 1 - k turns negative at r = n and repeat throws. The folded index must satisfy 0 ≤ k ≤ n - 1 for every r.
• println versus print. The string already ends with \n.

Related problems

• Pattern 7 is the upper half on its own.
• Pattern 8 is the lower half on its own.
• Pattern 10 applies the same folded-index idea to a left-aligned half diamond.