Topics › Basics › Patterns

Pattern 8

Easy TUF ID 421 A2Z

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

Given an integer n, print an inverted centred pyramid of stars with n rows. The first row is 2n - 1 stars starting at the left margin; each following row has two fewer stars and one more leading space, so the last row is a single star under the centre of the first.

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 = 4

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

Leading spaces 0, 1, 2, 3 and star counts 7, 5, 3, 1.

Example 2

n = 2

***
 *

The smallest case that shows both the shrinking stars and the growing indent.

Deriving the two formulas

Each row has two parts, a run of spaces and a run of stars, so we need two formulas in the 0-based row index i.

• Spaces: the first row has none and each row adds one, so row i has i spaces.
• Stars: the first row has 2n - 1 and each row removes two (one from each side), so row i has 2n - 1 - 2i = 2(n - i) - 1 stars.

Check the last row, i = n - 1: n - 1 spaces and 2(1) - 1 = 1 star. The lone star sits at column n - 1, exactly the centre of the 2n - 1 wide first row. That consistency check is worth doing on every pattern: plug in the first and last row and make sure both come out right.

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

Approach 1: Nested loops

Intuition. For row i, one inner loop appends i spaces and a second appends 2(n - i) - 1 stars, followed by a newline.

Algorithm.

1. For i from 0 to n - 1:
2. Append i spaces.
3. Append 2(n - i) - 1 stars.
4. Append \n.

static String nestedLoops(int n) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < n; i++) {
        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): row i has i + 2(n - i) - 1 = 2n - 1 - i characters, summing to about 1.5 n^2. Space O(n^2) for the output, O(1) extra.

Dry run for n = 3:

Each row is one character shorter than the one above it (one space gained, two stars lost), which is why the right edge of the pyramid also slopes inward even though we print no trailing spaces.

Approach 2: String.repeat

Intuition. With the two formulas in hand, the row is literally " ".repeat(i) + "*".repeat(2 * (n - i) - 1). Writing it this way makes the formulas the whole program, so an error in them is easy to spot and to test.

Algorithm.

1. For i from 0 to n - 1: append " ".repeat(i), then "*".repeat(2 * (n - i) - 1), then \n.

static String repeat(int n) {
    StringBuilder out = new StringBuilder();
    for (int i = 0; i < n; i++) {
        out.append(" ".repeat(i)).append("*".repeat(2 * (n - i) - 1)).append('\n');
    }
    return out.toString();
}

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

Both counts are non-negative for 0 ≤ i ≤ n - 1; repeat throws on a negative argument, so this is the place to double-check the range when adapting the formula.

Approach 3: Build the upright pyramid and flip it

Intuition. Rows of the inverted pyramid are rows of the upright pyramid in reverse order: our row i is the upright row n - 1 - i. The upright row k has n - 1 - k spaces and 2k + 1 stars. Substituting k = n - 1 - i gives i spaces and 2(n - 1 - i) + 1 = 2(n - i) - 1 stars, the same formulas as above, which confirms them from a different direction. So generate the upright rows into a list and emit them from the last to the first.

Algorithm.

1. For k from 0 to n - 1, add " ".repeat(n - 1 - k) + "*".repeat(2k + 1) to a list.
2. For k from n - 1 down to 0, append the row and \n.

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

Dry run for n = 3:

Emitted in reverse: "*****\n ***\n *\n".

Complexity. Time O(n^2), space O(n^2) for the list of rows plus the output.

Edge cases and pitfalls

• n = 0. Returns "".
• n = 1. A single "*\n": zero spaces and 2(1) - 1 = 1 star.
• Star formula. 2(n - i) - 1, not 2(n - i) + 1 or 2n - i. The first row must have 2n - 1 stars and the last row exactly one. Plugging in i = 0 and i = n - 1 catches most slips.
• Trailing spaces. Printing symmetric spaces on the right makes the output look the same but fail an exact comparison. This article omits them.
• Negative repeat count. If a loop bound is off by one and i reaches n, "*".repeat(-1) throws IllegalArgumentException. The exception is loud, which is better than silent garbage, but the fix is the loop bound.
• Tabs. Never indent with \t; the output must use real spaces.
• println versus print. The string already ends with \n.

Related problems

• Pattern 7 is this pyramid upright; Approach 3 is that pattern reversed.
• Pattern 9 combines the two into a diamond.
• Pattern 5 is the left-aligned inverted triangle without leading spaces.