Topics › Basics › Patterns

Pattern 2

Easy TUF ID 412 A2Z

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

Given an integer n, print a right-angled triangle of stars: n rows, where row i (counting from 1) contains exactly i stars separated by single spaces. The right angle sits at the bottom left, so the first row is one star and the last row is n stars.

Output format: every row ends with a newline, stars in a row are separated by one space, and there is no trailing space. n = 0 prints nothing.

Constraints: 0 ≤ n ≤ 100 is typical.

Example 1

n = 4

*
* *
* * *
* * * *

Row i has i stars, so the row widths are 1, 3, 5, 7 characters.

Example 2

n = 2

*
* *

The smallest case that shows the growth: the second row has one more star than the first.

The one idea this pattern adds

In the square pattern both loops run to n. Here the number of columns in a row depends on which row you are in: row i has i cells. In code that means the inner loop’s bound is the outer loop’s variable, for (j = 1; j <= i; j++). Almost every later pattern is some variation of this dependency, so it is worth being precise about it: the outer loop decides the row, the inner loop’s limit is a function of that row, and the body decides what to print in one cell.

As in the other pattern articles, each approach returns the pattern as a String so that main can compare it against expected literals. The caller prints it with one System.out.print.

Approach 1: Nested loops

Intuition. Row i needs i stars, so let the inner counter j run from 1 to i. A space goes between stars, which means before every star except the first in its row, hence the j > 1 check. After the inner loop, close the row with a newline.

Algorithm.

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

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

Complexity. Time O(n^2): the total number of stars is 1 + 2 + ... + n = n(n+1)/2. Space O(n^2) for the output; O(1) extra.

That n(n+1)/2 is the triangular number, and it is a good habit to compute it: it tells you that even for n = 10^4 the output is about 50 million stars, which is the real limit on n in any pattern problem, not the loop count.

Approach 2: Grow one row incrementally

Intuition. Look at consecutive rows: "*", "* *", "* * *". Each row is the previous row with " *" appended. So instead of rebuilding every row from scratch, keep one row buffer, extend it by one star per iteration, and copy it into the output. The inner loop disappears; the dependency on i is now expressed by the state carried from one row to the next.

This incremental view is how you would answer a follow-up like “print only row k” or “what is the total width after k rows” without re-running the inner loop.

Algorithm.

1. Keep two builders: out for the result and row for the current row.
2. For i from 1 to n: if i > 1 append a space to row; append * to row; append row and \n to out.
3. Return out.

static String growingRow(int n) {
    StringBuilder out = new StringBuilder();
    StringBuilder row = new StringBuilder();
    for (int i = 1; i <= n; i++) {
        if (i > 1) row.append(' ');
        row.append('*');
        out.append(row).append('\n');
    }
    return out.toString();
}

Complexity. Time O(n^2), because copying row into out costs i characters at step i, which again sums to n(n+1)/2. Space O(n) extra for the row buffer.

Approach 3: Describe each row with a stream

Intuition. A row is fully determined by its index i: it is i stars joined by spaces. Collections.nCopies(i, "*") gives the stars, String.join(" ", ...) glues them, and an IntStream over 1..n maps each index to its row and concatenates. This reads like the specification of the pattern rather than like a procedure, and it is a good exercise in IntStream.mapToObj and Collectors.joining.

Algorithm.

1. IntStream.rangeClosed(1, n) produces the row indices.
2. mapToObj turns index i into join(" ", nCopies(i, "*")) + "\n".
3. Collectors.joining() concatenates the rows.

static String streams(int n) {
    return IntStream.rangeClosed(1, n)
            .mapToObj(i -> String.join(" ", Collections.nCopies(i, "*")) + "\n")
            .collect(Collectors.joining());
}

Dry run for n = 3:

Joined: "*\n* *\n* * *\n".

Complexity. Time O(n^2) for the same reason as before. Space O(n) extra per row being built. For n = 0 the range is empty and the result is "", so no special case is needed.

Edge cases and pitfalls

• n = 0. Produces "". Every approach handles this naturally because its loop or stream is empty.
• n = 1. One star and no space. The separator check (j > 1 or i > 1) is what keeps the row free of stray spaces.
• 0-based versus 1-based. If you start i at 0, the inner loop must run j <= i to get i + 1 stars, or j < i prints an empty first row. Pick one convention and derive the bounds from it, rather than adjusting by trial and error.
• Trailing space. sb.append("* ") is tempting but leaves a trailing space on every row. Emit the separator before each star except the first.
• print versus println. The returned string ends in \n; printing it with println adds an extra empty line.
• Quadratic string concatenation. Building rows with row = row + " *" on String allocates a new object every step. StringBuilder avoids that; String.repeat and String.join are also fine because they allocate once per row.
• Confusing this with Pattern 4. Here the body prints a fixed character. When the body prints the loop variable, you get the number pyramids instead.

Related problems

• Pattern 1 is the square this triangle is cut from.
• Pattern 3 prints the column index j instead of a star.
• Pattern 5 is this triangle upside down.
• Pattern 10 glues this triangle to its mirror image.