Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Floyd's Triangle

Try it yourself
EasyProblem

Description

Given n, return the first n rows of Floyd's triangle, as a list of rows. The numbers 1, 2, 3, ... fill the rows in order: the first row holds 1 number, the second 2, the third 3, and so on. Within a row, the numbers are separated by single spaces.

Examples

Example 1

Input: n = 4

Output: ["1", "2 3", "4 5 6", "7 8 9 10"]

Explanation: 1; then 2 and 3; then 4, 5 and 6; then 7, 8, 9 and 10.

Example 2

Input: n = 1

Output: ["1"]

Explanation: Just 1.

Example 3

Input: n = 3

Output: ["1", "2 3", "4 5 6"]

Explanation: Three rows, ending at 6.

Constraints

  • 1 ≤ n ≤ 100

Editorial

Approach - Build Each Row from Its Counts

Intuition

One counter runs through the whole triangle. Row i takes the next i numbers from it, and the next row starts where this one stopped. Join each row's numbers with single spaces, so nothing comes before the first or after the last.

Step-by-Step Explanation

Let's trace Example 1, n = 4:

  1. Row 1: the next 1 number, 1.
  2. Row 2: the next 2 numbers, 2, 3.
  3. Row 3: the next 3 numbers, 4, 5, 6.
  4. Row 4: the next 4 numbers, 7, 8, 9, 10.
  5. Return the 4 rows.

Floyd's Triangle — The rows, built one per step from the top; the row just built is lit.

Algorithm

  1. Start a counter at 1.
  2. For i from 1 to n: take the next i values of the counter, join them with spaces, and add the row.
  3. Return the rows.

Code

class Solution {
public:
    vector<string> floydsTriangle(int n) {
        vector<string> rows;
        int k = 1;
        for (int i = 1; i <= n; i++) {
            string row;
            for (int j = 0; j < i; j++) {
                if (j > 0) row += ' ';
                row += to_string(k++);      // the next row starts where this one stopped
            }
            rows.push_back(row);
        }
        return rows;
    }
};

from typing import List

class Solution:
    def floydsTriangle(self, n: int) -> List[str]:
        rows, k = [], 1
        for i in range(1, n + 1):
            rows.append(" ".join(str(k + j) for j in range(i)))
            k += i                          # the next row starts where this one stopped
        return rows

import java.util.*;

class Solution {
    public List<String> floydsTriangle(int n) {
        List<String> rows = new ArrayList<>();
        int k = 1;
        for (int i = 1; i <= n; i++) {
            StringBuilder row = new StringBuilder();
            for (int j = 0; j < i; j++) {
                if (j > 0) row.append(' ');
                row.append(k++);            // the next row starts where this one stopped
            }
            rows.add(row.toString());
        }
        return rows;
    }
}

var floydsTriangle = function(n) {
    const rows = [];
    let k = 1;
    for (let i = 1; i <= n; i++) {
        const row = [];
        for (let j = 0; j < i; j++) row.push(k++);   // the next row starts where this one stopped
        rows.push(row.join(" "));
    }
    return rows;
};

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.

Restarting each row at 1. for j in range(1, i + 1)

On n = 4 it returns ["1", "1 2", "1 2 3", "1 2 3 4"]; the answer is ["1", "2 3", "4 5 6", "7 8 9 10"]. Floyd's numbers keep counting from one row to the next: row 2 is 2 3, not 1 2. One counter has to run through all the rows.

Leaving a space after each number. f"{k + j} "

On n = 4 it returns ["1 ", "2 3 ", "4 5 6 ", "7 8 9 10 "]; the answer is ["1", "2 3", "4 5 6", "7 8 9 10"]. Writing each number followed by a space leaves one at the end of the row. Spaces go between numbers, so join them with " ".

Counting from 0. rows, k = [], 0

On n = 4 it returns ["0", "1 2", "3 4 5", "6 7 8 9"]; the answer is ["1", "2 3", "4 5 6", "7 8 9 10"]. The triangle starts at 1. Starting the counter at 0 shifts every number down by one.

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.