Drawing shapes out of characters comes down to how many characters go on each line and how that count changes from line to line. A right-angled triangle is the simplest of these shapes, since each row is a run of stars with nothing else around it.

The rule is short. Row 1 has one star, row 2 has two stars, and the count climbs by one star per row until row n, which has n stars. If n is 4, the rows hold 1, 2, 3, and 4 stars, reading as the triangle *, **, ***, ****. Each row is returned as its own string, and the strings together make up the array.

The whole problem rests on one relationship: row i needs exactly i stars. The rest is turning that count into a string and collecting the strings in order.

Key Constraints:

Intuition

Handle one row at a time, laying down its stars one by one. An outer loop walks the row numbers from 1 to n. For each row number i, an inner loop runs i times, appending a star on every pass, which produces a string of exactly i stars.

The inner loop count is tied to the outer row number, so each new row ends up one star longer than the one before it.

Algorithm

Example Walkthrough

Input:

The outer loop starts at i = 1, and the inner loop runs once to build "*", which becomes the first row. At i = 2, the inner loop runs twice to build "**". At i = 3 it builds "***", and at i = 4 it builds "****". After i = 4, the outer loop stops because the next value would pass n. The four rows collected in order form the triangle:

Code

The inner loop rebuilds the run of stars from scratch on every row, even though each row only differs from the one above by a single star. Can we reuse the previous row instead of starting over?

Intuition

Each row is the previous row with one extra star at the end. Row 2 is row 1 plus a star, row 3 is row 2 plus a star, and so on. Instead of rebuilding the full run of stars every time, keep a single string that grows as you move down the triangle.

Before recording each row, append one star to that string. It now matches the current row, so add a copy of it to the result. This removes the inner loop: one append per row rather than rebuilding the whole row.

Algorithm

Example Walkthrough

Input:

The string row begins empty. On the first pass it becomes "*", which is added as row 1. On the second pass one more star makes it "**", added as row 2. The third pass turns it into "***", and the fourth pass turns it into "****". Each pass added a single star to the same string, and the recorded copies form the triangle:

Code