☕ DSA Java Articles

Topics › Basics › Patterns

Pattern 20

Medium TUF ID 413 A2Z

Java source ↗ Edit this article ↗

Problem

Given a positive integer n, print the symmetric butterfly: 2n - 1 rows, each 2n characters wide. Row r (counting from 1) has s stars at the left edge and s stars at the right edge with spaces in between, where s grows 1, 2, ..., n over the first n rows and then shrinks n - 1, ..., 1 over the remaining n - 1 rows. The middle row is solid.

Constraints: 1 ≤ n ≤ 50 or so; the output has about 4n^2 characters.

Example 1

n = 3
*    *
**  **
******
**  **
*    *

Five rows; the third is solid and the figure is mirrored around it.

Example 2

n = 5
*        *
**      **
***    ***
****  ****
**********
****  ****
***    ***
**      **
*        *

Nine rows of ten characters; the wings meet in row 5.

Reading the pattern

Each row is s stars, a gap, and s stars again, with a fixed width of 2n, so the gap is 2n - 2s = 2(n - s). As with every “two sides and a gap” figure, the row is fully described by s, and the pattern is the sequence of star counts

1, 2, ..., n-1, n, n-1, ..., 2, 1

for rows r = 1 .. 2n - 1. The sequence rises to n at the middle row r = n and falls symmetrically, which is exactly s = n - |n - r|: the distance of r from the middle, subtracted from the peak.

Two implementations follow. The first writes two loops, one per wing, mirroring each other. The second uses the absolute-value formula to handle both wings in a single loop. Both return the finished picture as one String with a newline after every row, so main can compare them against expected strings and structural properties (palindromic rows, vertical mirror symmetry, a solid middle row) for n up to 20.

Approach 1: Two wings, three loops per row

Intuition. The upper wing has rows with i = 1 .. n stars per side; the lower wing has rows with i = n - 1 .. 1 stars per side. Both wings use the same row recipe: i stars, 2(n - i) spaces, i stars. So write the recipe twice, once under a rising loop and once under a falling loop.

Algorithm.

  1. For i from 1 to n: append i stars, 2(n - i) spaces, i stars, newline.
  2. For i from n - 1 down to 1: append i stars, 2(n - i) spaces, i stars, newline.
static String nestedLoops(int n) {
    StringBuilder sb = new StringBuilder();
    for (int i = 1; i <= n; i++) {                      // upper wing, i stars each side
        for (int j = 0; j < i; j++) sb.append('*');
        for (int j = 0; j < 2 * (n - i); j++) sb.append(' ');
        for (int j = 0; j < i; j++) sb.append('*');
        sb.append('\n');
    }
    for (int i = n - 1; i >= 1; i--) {                  // lower wing, i stars each side
        for (int j = 0; j < i; j++) sb.append('*');
        for (int j = 0; j < 2 * (n - i); j++) sb.append(' ');
        for (int j = 0; j < i; j++) sb.append('*');
        sb.append('\n');
    }
    return sb.toString();
}

Complexity. Time O(n^2): 2n - 1 rows of 2n characters each. Space O(n^2) for the output; constant extra memory.

The lower loop starts at n - 1, not n, so the solid row is printed exactly once. Starting it at n produces two solid rows and 2n rows in total, which is a different figure.

Approach 2: One loop with s = n - |n - r|

Intuition. The star count rises linearly to the middle row and falls linearly after it. “Distance from the middle” is |n - r|, and the count is the peak minus that distance. One loop over r = 1 .. 2n - 1 with this formula removes the duplicated recipe, and String.repeat builds each row from three pieces.

Algorithm.

  1. For r from 1 to 2n - 1: let s = n - |n - r|.
  2. Let side = "*".repeat(s).
  3. Append side, " ".repeat(2(n - s)), side, newline.
static String formula(int n) {
    StringBuilder sb = new StringBuilder();
    for (int r = 1; r <= 2 * n - 1; r++) {
        int stars = n - Math.abs(n - r);                // 1, 2, ..., n, ..., 2, 1
        String side = "*".repeat(stars);
        sb.append(side).append(" ".repeat(2 * (n - stars))).append(side).append('\n');
    }
    return sb.toString();
}

Dry run for n = 3:

r n - r stars gap row
1 2 1 4 * *
2 1 2 2 ** **
3 0 3 0 ******
4 -1 2 2 ** **
5 -2 1 4 * *

Complexity. Time O(n^2): three repeat calls per row with total length 2n. Space O(n^2) for the output plus O(n) of short-lived temporaries per row.

The formula view also explains the symmetry directly: rows r and 2n - r have |n - r| and |n - (2n - r)| = |r - n| respectively, the same distance, hence the same row. The tests assert rows[r] == rows[2n - 2 - r] (0-based) for every n.

Edge cases and pitfalls