Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Butterfly Pattern

Try it yourself
EasyProblem

Description

Given n, return a butterfly of stars, 2n rows high, as a list of rows. In the top half, row i, from 1 to n, is i stars, 2(n - i) spaces and i stars, so the two wings grow until they meet in a full row of 2n stars. The bottom half is the top half upside down.

Examples

Example 1

Input: n = 3

Output: ["* ", "* ", "", "****", " *", " *"]

Explanation: Each wing grows from 1 star to 3 while the gap closes from 4 spaces to none; then the same rows in reverse.

Example 2

Input: n = 1

Output: ["", ""]

Explanation: Two rows of 2 stars.

Example 3

Input: n = 2

Output: ["* ", "", "**", " *"]

Explanation: * *, then two full rows of 4, then * * again.

Constraints

  • 1 ≤ n ≤ 100

Editorial

Approach - Build Each Row from Its Counts

Intuition

Every row is 2n characters wide: a left wing, a gap and a right wing. In the top half the wings are i stars each and the gap takes what's left, 2(n - i). The bottom half mirrors the top, including its full row, so that row appears twice in the middle.

Step-by-Step Explanation

Let's trace Example 1, n = 3:

  1. Row 1: 1 star, 4 spaces, 1 star.
  2. Row 2: 2 stars, 2 spaces, 2 stars.
  3. Row 3: 3 stars, 0 spaces, 3 stars.
  4. Row 4: 3 stars, 0 spaces, 3 stars.
  5. Row 5: 2 stars, 2 spaces, 2 stars.
  6. Row 6: 1 star, 4 spaces, 1 star.
  7. Return the 6 rows.

Butterfly Pattern — The rows, built one per step from the top; the row just built is lit.

Algorithm

  1. Build the top half: for i from 1 to n, a row of i stars, 2(n - i) spaces and i stars.
  2. Add the top half again in reverse.
  3. Return all 2n rows.

Code

class Solution {
public:
    vector<string> butterfly(int n) {
        vector<string> top;
        for (int i = 1; i <= n; i++) top.push_back(string(i, '*') + string(2 * (n - i), ' ') + string(i, '*'));
        vector<string> rows = top;
        rows.insert(rows.end(), top.rbegin(), top.rend());
        return rows;
    }
};

from typing import List

class Solution:
    def butterfly(self, n: int) -> List[str]:
        top = ["*" * i + " " * (2 * (n - i)) + "*" * i for i in range(1, n + 1)]
        return top + top[::-1]

import java.util.*;

class Solution {
    public List<String> butterfly(int n) {
        List<String> top = new ArrayList<>();
        for (int i = 1; i <= n; i++) top.add("*".repeat(i) + " ".repeat(2 * (n - i)) + "*".repeat(i));
        List<String> rows = new ArrayList<>(top);
        for (int i = n - 1; i >= 0; i--) rows.add(top.get(i));
        return rows;
    }
}

var butterfly = function(n) {
    const top = [];
    for (let i = 1; i <= n; i++) top.push("*".repeat(i) + " ".repeat(2 * (n - i)) + "*".repeat(i));
    return [...top, ...[...top].reverse()];
};

Complexity Analysis

Time Complexity: O(n²)

There are O(n) rows of O(n) characters, and each character is written once.

Space Complexity: O(n²)

The rows of the answer.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Writing the middle row once. return top + top[-2::-1]

On n = 3 it returns ["* *", "** **", "******", "** **", "* *"]; the answer is ["* *", "** **", "******", "******", "** **", "* *"]. The butterfly's two halves each end in a full row of 2n stars, so that row appears twice. Reversing the top half without its last row leaves one of them out.

Making the gap one space too narrow. 2 * (n - i) - 1

On n = 3 it returns ["* *", "** **", "******", "******", "** **", "* *"]; the answer is ["* *", "** **", "******", "******", "** **", "* *"]. Each row is 2n characters wide: two wings of i stars leave 2(n - i) spaces between them. One space fewer makes every row but the full ones one character short.

Building only the top half. return ["*" * i + " " * (2 * (n - i)) + "*" * i for i in range(1, n + 1)]

On n = 3 it returns ["* *", "** **", "******"]; the answer is ["* *", "** **", "******", "******", "** **", "* *"]. The wings open again below the middle: the bottom half is the top half upside down, n more rows.

Where This Pattern Is Taught

This problem practises nested counting: for each row, how many of each character, and building the row as a string. It's taught in Python for DSA, Java for DSA, C++ for DSA and JavaScript for DSA.