Topics › Basics › Patterns

Pattern 5

Easy TUF ID 418 A2Z

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

Given an integer n, print an inverted right-angled triangle of stars: n rows, where the first row contains n stars, the second n - 1, and so on down to a final row with a single star. Stars in a row are separated by single spaces.

Output format: every row ends with a newline, exactly one space between stars, no trailing space. n = 0 prints nothing.

Constraints: 0 ≤ n ≤ 100 is typical.

Example 1

n = 4

* * * *
* * *
* *
*

Row i (0-based) has n - i stars: 4, 3, 2, 1.

Example 2

n = 1

*

The full row and the single-star row coincide.

The idea: a bound that decreases

In the upright triangle of Pattern 2, row i has i stars and the inner bound grows with the row. Here it shrinks: using a 0-based row index i, the row has n - i stars. Nothing else changes. If you prefer to think in 1-based rows, row i has n - i + 1 stars; both are the same pattern, and the only skill being tested is deriving the inner bound from the row index without off-by-one mistakes.

There is a second, more structural way to see it: this pattern is Pattern 2 read bottom-to-top. Approach 3 exploits that directly.

Every approach returns the pattern as a String so the tests can compare it with expected literals.

Approach 1: Nested loops

Intuition. The outer loop runs i over 0..n-1; the inner loop runs j over 0..n-i-1, giving n - i stars. The separator is placed before every star except the first, so there is no trailing space.

Algorithm.

1. For i from 0 to n - 1:
2. For j from 0 to n - i - 1: if j > 0 append a space; append *.
3. Append \n.
4. Return the string.

static String nestedLoops(int n) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - i; j++) {
            if (j > 0) sb.append(' ');
            sb.append('*');
        }
        sb.append('\n');
    }
    return sb.toString();
}

Complexity. Time O(n^2): n + (n-1) + ... + 1 = n(n+1)/2 stars. Space O(n^2) for the output, O(1) extra.

Check the boundary rows: for i = 0 the inner loop runs n times, for i = n - 1 it runs once. If you accidentally write j < n - i - 1, the last row becomes empty and the first row is one star short.

Approach 2: Shrink one row in place

Intuition. Consecutive rows are "* * * *", "* * *", "* *", "*". Each row is the previous one with its last two characters (" *") removed. So build the full row once, and after emitting each row, cut two characters off the end with StringBuilder.setLength. This is the mirror image of the “grow a row” technique for the upright triangle, and it shows that setLength is a cheap way to truncate a builder.

Algorithm.

1. row = "* * ... *" with n stars (built via nCopies and join).
2. For i from 0 to n - 1: append row and \n to the output; set row’s length to max(0, length - 2).
3. Return the output.

static String shrinkingRow(int n) {
    StringBuilder out = new StringBuilder();
    StringBuilder row = new StringBuilder(String.join(" ", Collections.nCopies(n, "*")));
    for (int i = 0; i < n; i++) {
        out.append(row).append('\n');
        row.setLength(Math.max(0, row.length() - 2));
    }
    return out.toString();
}

Complexity. Time O(n^2) for copying the rows into the output. Space O(n) extra for the row buffer.

The Math.max(0, ...) guard matters only on the last iteration: the row is "*" (length 1) and length - 2 would be -1, which setLength rejects with an exception. Clamping to 0 keeps the code uniform.

Approach 3: Build the upright triangle and reverse it

Intuition. Row k of the upright triangle (1-based) has k stars. Our pattern lists those rows from k = n down to k = 1. So generate the upright rows into a list and reverse the list. Composition like this is how you should approach every more complicated pattern: identify a simpler pattern you already have, and describe the new one as a transformation of it.

Algorithm.

1. For k from 1 to n, add join(" ", nCopies(k, "*")) to a list.
2. Collections.reverse the list.
3. Append each row followed by \n.

static String reversedTriangle(int n) {
    List<String> rows = new ArrayList<>();
    for (int i = 1; i <= n; i++) rows.add(String.join(" ", Collections.nCopies(i, "*")));
    Collections.reverse(rows);
    StringBuilder out = new StringBuilder();
    for (String row : rows) out.append(row).append('\n');
    return out.toString();
}

Dry run for n = 3:

Complexity. Time O(n^2), space O(n^2) for the list of rows (it holds the whole pattern once) plus the output.

Edge cases and pitfalls

• n = 0. All methods return "". In Approach 2 the initial row is also "" and the loop never runs.
• n = 1. One row, one star, no separator.
• Off-by-one in the shrinking bound. j < n - i gives n - i stars for 0-based i. Writing j <= n - i prints one extra star per row; writing j < n - i - 1 drops one.
• 1-based confusion. If you loop i from 1 to n, the bound is n - i + 1, not n - i. Derive the bound from the row count you want rather than guessing.
• Negative setLength. StringBuilder.setLength(-1) throws StringIndexOutOfBoundsException. Clamp with Math.max(0, ...) or stop shrinking before the last row.
• Trailing space. Append the separator before every star except the first. Appending "* " leaves a space at the end of every row.
• println versus print. The string already ends with \n.

Related problems

• Pattern 2 is this triangle upright; Approach 3 is literally that pattern reversed.
• Pattern 6 is the same inverted shape with numbers instead of stars.
• Pattern 8 is the inverted centred pyramid, where leading spaces appear.