Floyd’s triangle

Easy TimeO(n²) SpaceO(n²)

Given a row count n, return Floyd’s triangle as an array of n strings: the counting numbers laid out in rows of growing length, row 1 holding one number, row 2 the next two, row n the next n. The numbering runs on across rows and never restarts, and the numbers within a row are separated by a single space.

Examples

Example 1

Input
n = 5
Output
1
2 3
4 5 6
7 8 9 10
11 12 13 14 15
["1","2 3","4 5 6","7 8 9 10","11 12 13 14 15"]
Fifteen numbers over five rows, and row 5 begins where row 4 stopped.

Example 2

Input
n = 3
Output
1
2 3
4 5 6
["1","2 3","4 5 6"]
Three rows use 1 + 2 + 3 = 6 numbers, so the last one is 6.

The Code

function floydsTriangle(n) {
  const rows = [];
  let counter = 1;
  for (let row = 1; row <= n; row++) {
    const line = [];
    for (let col = 1; col <= row; col++) {
      line.push(counter);
      counter++;
    }
    rows.push(line.join(" "));
  }
  return rows;
}
floydsTriangle(5);
Done

The first 19 calls, of 27. This one does not fit on a page.

Step through floydsTriangle(5) call by call

Explanation

The rows only decide where the line breaks fall; the numbers are one uninterrupted count. What a row opens with is whatever the row before it left off at — the one thing a row cannot work out on its own.

  1. 1

    counter is declared before either loop, so there is one of it for the whole run. row is 1, the inner loop runs once, and it pushes counter onto line before counter++ moves it on.

    1
    0

    counter=1row=1

    rows.push("1")

  2. 2

    row is 2. line is a fresh array — it is declared inside the outer loop — but counter is not: it comes into this row still holding 2, so the row takes 2 and 3.

    1
    0
    2 3
    1

    counter=2row=2

    rows.push("2 3")

  3. 3

    row is 3, and counter picks up at 4 because that is where row 2 left it. What a row starts with is not a fact about the row; it is whatever the row before it stopped at.

    1
    0
    2 3
    1
    4 5 6
    2

    counter=4row=3

    rows.push("4 5 6")

  4. 4

    row is 4 and counter is at 7, so the row takes 7, 8, 9 and 10. Declaring counter inside the outer loop instead would reset it to 1 here and the row would read 1 2 3 4.

    1
    0
    2 3
    1
    4 5 6
    2
    7 8 9 10
    3

    counter=7row=4

    rows.push("7 8 9 10")

  5. 5

    row is 5 and counter is at 11, so the last row takes 11 through 15. line.join(" ") puts a single space between them and the five strings are returned.

    1
    0
    2 3
    1
    4 5 6
    2
    7 8 9 10
    3
    11 12 13 14 15
    4

    counter=11row=5

    return rows → 5 rows

More like this

All star & number patterns examples (12) →