Topics › Basics › Patterns

Pattern 10

Easy TUF ID 402 A2Z

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

Given an integer n, print a left-aligned half diamond of stars: the star counts per row go 1, 2, ..., n, n - 1, ..., 1. There are 2n - 1 rows, the single widest row has n stars, and there are no spaces anywhere, neither between stars nor as padding.

Output format: every row ends with a newline. n = 0 prints nothing.

Constraints: 0 ≤ n ≤ 100 is typical.

Example 1

n = 4

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

Seven rows: the count climbs to 4 and then descends.

Example 2

n = 1

*

2n - 1 = 1 row. The climb and the descent share their single row.

From two loops to one formula

The natural first solution is two phases: a loop that prints 1..n stars per row (the right-angled triangle), then a loop that prints n - 1 .. 1. That is correct and easy to reason about. The more interesting question is whether the star count can be written as one function of the row number i running from 1 to 2n - 1. It can: stars(i) = i while i ≤ n, and stars(i) = 2n - i afterwards. At i = n both expressions give n, so the two pieces meet without a gap, and the second expression reaches 1 exactly at i = 2n - 1. The compact form of the same thing is min(i, 2n - i).

Writing a symmetric sequence as min of an increasing and a decreasing linear function is a reusable trick. It appears again in the full diamond and in many “mountain” or “peak” shaped sequences.

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

Approach 1: Two loops, up then down

Intuition. Phase one prints rows with 1, 2, ..., n stars. Phase two prints rows with n - 1, n - 2, ..., 1 stars. The widest row belongs to phase one only, which is what keeps the total at 2n - 1 rows.

Algorithm.

1. For i from 1 to n: append i stars and \n.
2. For i from n - 1 down to 1: append i stars and \n.
3. Return the string.

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

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

Watch the second loop’s start: it begins at n - 1, not n, otherwise the widest row is printed twice (that doubled-middle shape is a different pattern).

Approach 2: One loop with a folded star count

Intuition. Run i over all 2n - 1 rows and compute the star count with the piecewise formula: i while climbing, 2n - i while descending. The two phases become one loop with a conditional expression; the shape of the output is now entirely captured by that expression.

Algorithm.

1. For i from 1 to 2n - 1: stars = (i <= n) ? i : 2n - i.
2. Append stars stars and \n.

static String foldedIndex(int n) {
    StringBuilder sb = new StringBuilder();
    for (int i = 1; i <= 2 * n - 1; i++) {
        int stars = i <= n ? i : 2 * n - i;
        for (int j = 0; j < stars; j++) sb.append('*');
        sb.append('\n');
    }
    return sb.toString();
}

Dry run for n = 3 (rows i = 1..5):

Complexity. Time O(n^2), space O(1) extra.

Approach 3: min inside a stream

Intuition. min(i, 2n - i) is the same fold without a branch, and a stream makes the whole pattern one expression: the row indices 1..2n - 1, mapped to star counts, mapped to rows of "*".repeat(count), concatenated. The pipeline reads as the specification: “for each row, that many stars”.

Algorithm.

1. IntStream.rangeClosed(1, 2n - 1).
2. map(i -> Math.min(i, 2n - i)) gives star counts.
3. mapToObj(stars -> "*".repeat(stars) + "\n") and Collectors.joining().

static String streams(int n) {
    return IntStream.rangeClosed(1, 2 * n - 1)
            .map(i -> Math.min(i, 2 * n - i))
            .mapToObj(stars -> "*".repeat(stars) + "\n")
            .collect(Collectors.joining());
}

Complexity. Time O(n^2), space O(n) extra for one row at a time.

For n = 0 the range is 1..-1, which is empty, so the result is "" with no special case. For n = 1 the range is 1..1 and min(1, 1) = 1, giving a single star.

Edge cases and pitfalls

• n = 0. All methods return "". In Approach 1 the first loop does not run and the second starts at -1, which fails i >= 1 immediately.
• n = 1. One row. The formula min(1, 2 - 1) = 1 confirms it.
• Doubling the middle row. Starting the descent at n instead of n - 1, or using 2n + 1 - i in the fold, prints the widest row twice and gives 2n rows. Count your rows: this pattern has 2n - 1.
• Off-by-one in the fold. The descending expression must hit 1 at the last row i = 2n - 1: 2n - (2n - 1) = 1. If you get 0, you have an empty last line.
• No separators. Unlike the earlier triangles, stars here are adjacent. Appending "* " out of habit produces a different pattern.
• repeat with a negative count. If the loop overruns to i = 2n, min(2n, 0) = 0 is fine, but i = 2n + 1 gives -1 and repeat throws. Keep the range exact.
• println versus print. The returned string already ends with \n.

Related problems

• Pattern 2 is the climbing half on its own, with spaces between stars.
• Pattern 9 is the centred diamond, solved with the same folded index.
• Pattern 5 is the descending half as a standalone pattern.