Butterfly pattern

Medium TimeO(n²) SpaceO(n²)

Given a half-height n, return the butterfly as an array of 2n − 1 strings: two triangles of stars facing outwards with a gap between them. Row i of the upper half holds i stars, then 2(n − i) spaces, then i stars again, and the rows after the middle repeat the upper half in reverse. Every row is the same width, 2n characters, and the middle row has no gap at all.

Examples

Example 1

Input
n = 4
Output
*      *
**    **
***  ***
********
***  ***
**    **
*      *
["* *","** **","*** ***","********","*** ***","** **","* *"]
Eight characters on every row: 1 + 6 + 1, then 2 + 4 + 2, then 3 + 2 + 3, then 8.

Example 2

Input
n = 2
Output
*  *
****
*  *
["* *","****","* *"]
Three rows of four characters, and the middle row spends all four on stars.

The Code

function butterfly(n) {
  const rows = [];
  function wing(stars) {
    let line = "";
    for (let i = 0; i < stars; i++) line += "*";
    for (let i = 0; i < (n - stars) * 2; i++) line += " ";
    for (let i = 0; i < stars; i++) line += "*";
    return line;
  }
  for (let row = 1; row <= n; row++) {
    rows.push(wing(row));
  }
  for (let row = n - 1; row >= 1; row--) {
    rows.push(wing(row));
  }
  return rows;
}
butterfly(4);
Done

The first 18 calls, of 93. This one does not fit on a page.

Step through butterfly(4) call by call

Explanation

Each row spends the same 2n characters on two wings and the gap between them. Whatever the wings take, the gap gives up, so the outer edges stay straight while the inner ones close. Each space is drawn as · in the rows below.

  1. 1

    row is 1, so wing(1) runs: one *, then (n - stars) * 2 = 6 spaces, then one * again. The helper returns the finished string and the loop pushes it.

    *······*
    0

    stars=1(n - stars) * 2=6

    rows.push("*······*")

  2. 2

    row is 2 — wing(2). Each wing takes one more star, so the gap has to give up two, and the row is still eight characters wide.

    *······*
    0
    **····**
    1

    stars=2(n - stars) * 2=4

    rows.push("**····**")

  3. 3

    row is 3 — wing(3): three stars, two spaces, three stars.

    *······*
    0
    **····**
    1
    ***··***
    2

    stars=3(n - stars) * 2=2

    rows.push("***··***")

  4. 4

    row is 4, which is n, so (n - stars) * 2 is 0 and the middle loop of wing does not run: the two wings meet. row++ then ends the first loop.

    *······*
    0
    **····**
    1
    ***··***
    2
    ********
    3

    stars=4(n - stars) * 2=0

    rows.push("********")

  5. 5

    The second loop opens at n - 1, which is 3. Opening at n would call wing(4) again and the butterfly would carry two closed rows.

    *······*
    0
    **····**
    1
    ***··***
    2
    ********
    3
    ***··***
    4

    row=3rows.length=4

    rows.push("***··***")

  6. 6

    row counts down through 2 and 1, calling wing with the same numbers the first loop used, so the rows come back out in reverse. At 0 it fails row >= 1 and the seven strings are returned.

    *······*
    0
    **····**
    1
    ***··***
    2
    ********
    3
    ***··***
    4
    **····**
    5
    *······*
    6

    row=2 then 1rows.length=5

    return rows → 7 rows

More like this

All star & number patterns examples (12) →