Print a Butterfly Star Pattern

Easy15 min

Topics

BasicsPatternsLoops

Companies

TCSInfosysWipro

Given n, return the 2n rows of a butterfly: a left wing and a right wing of stars that grow towards the middle, meet in two full rows, and then shrink back. Each row has three parts — a wing, a gap and an identical wing — and the gap shrinks by exactly as much as the wings grow, so row width stays fixed at 2n. Seeing a row as repeated parts is the key to most "symmetric" patterns.

Test Case 1:

Input:n = 3

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

Explanation:Two wings grow towards each other until they touch in the middle, then shrink back.

Test Case 2:

Input:n = 1

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

Explanation:Each wing is a single star and there is no gap between them.

Constraints

◆1 ≤ n ≤ 20

Try the Dry Run

Mode

Approach

Approach & Solutions

Nested Loops — Wing, Gap, WingGood

There are 2n rows; let k rise 1..n over the top half and fall n..1 over the bottom half. Every row is k stars, then 2(n − k) spaces, then k stars, so every row is exactly 2n characters wide. Three inner loops write the three parts.

TimeO(n²)

SpaceO(n²) for the output

Java

Try it out

class Solution {
    public String[] printButterfly(int n) {
        String[] result = new String[2 * n];
        for (int r = 0; r < 2 * n; r++) {
            int k = r < n ? r + 1 : 2 * n - r;
            StringBuilder row = new StringBuilder();
            for (int j = 0; j < k; j++) {
                row.append('*');
            }
            for (int s = 0; s < 2 * (n - k); s++) {
                row.append(' ');
            }
            for (int j = 0; j < k; j++) {
                row.append('*');
            }
            result[r] = row.toString();
        }
        return result;
    }
}

Repeat One Wing TwiceOptimal

Both wings of a row are identical, so build the wing once with a built-in repeat and place it on both sides of the gap. C fills the row with spaces and then writes k stars at each end with memset.