Floyd's Triangle writes the counting numbers in a triangular shape. You start at 1 in the top-left corner and keep counting upward, while the rows grow as you go down: the first row holds one number, the second holds two, the third holds three, for as many rows as you ask for.

The numbers never restart. Once you write 1 in the first row, the next row picks up at 2 and 3, the row after that runs 4, 5, 6, and so on. So the value in any cell depends only on how many numbers came before it, not on which row it sits in.

For n = 3 the triangle is [[1], [2, 3], [4, 5, 6]], and for n = 1 it is [[1]]. The task is to return these rows as a list, where each inner list is one row.

Key Constraints:

Intuition

Since the numbers flow continuously from one row into the next, carry a single counter across all the rows. Start it at 1, and each time you place a value into a cell, write the counter and then increment it.

The rows only change how many cells you fill before moving on. Row i needs i numbers, so you fill i cells from the shared counter and then start a new row. Because the counter is never reset, row 2 begins where row 1 left off.

Algorithm

Example Walkthrough

Input:

The counter num starts at 1. Row 1 needs one number, so it takes 1 and the counter moves to 2. Row 2 needs two numbers, so it takes 2 and 3, leaving the counter at 4. Row 3 needs three numbers, so it takes 4, 5, and 6. After the third row the loop ends, and the rows collected so far form the triangle:

Code

The running counter ties the rows together, but it forces you to fill the rows in order so the counter stays correct. What if you wanted to compute any row on its own, without filling the rows above it first?

Intuition

Each row starts right after the previous rows end, so the first number in a row depends only on how many numbers came before it. Rows 1 through i - 1 together hold 1 + 2 + ... + (i - 1) numbers, which is the triangular number i × (i - 1) / 2. The first value of row i is one more than that count, so it equals i × (i - 1) / 2 + 1.

Once you know where a row begins, filling it is easy. The numbers in a row are consecutive, so row i runs from its starting value through the next i - 1 values. This lets you build each row directly from its index without carrying any state from earlier rows.

Algorithm

Example Walkthrough

Input:

For row 1, the start is 1 × 0 / 2 + 1 = 1, so the row is [1]. For row 2, the start is 2 × 1 / 2 + 1 = 2, and the two consecutive numbers are 2 and 3. For row 3, the start is 3 × 2 / 2 + 1 = 4, and the three consecutive numbers are 4, 5, and 6. Each row was computed from its index alone, and together they form the triangle:

Code