☕ DSA Java Articles

Topics › Basics › Patterns

Pattern 13

Easy TUF ID 405 A2Z

Java source ↗ Edit this article ↗

Problem

Given a positive integer n, print the increasing number triangle: n rows where row i (counting from 1) contains i numbers, and the numbers keep counting up across rows without ever restarting. Row 1 holds 1, row 2 holds 2 3, row 3 holds 4 5 6, and so on. Numbers in a row are separated by single spaces.

Constraints: 1 ≤ n ≤ 1000 is plenty for a printing exercise; the last number printed is n(n+1)/2, so for n = 1000 it is 500500.

Example 1

n = 4
1
2 3
4 5 6
7 8 9 10

Four rows, ten numbers in total, each row one number longer than the last.

Example 2

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

The fifth row starts at 11 because the first four rows used up 1 + 2 + 3 + 4 = 10 numbers.

Reading the pattern

Two things describe this pattern completely:

  1. Shape. Row i has i entries. The shape is a right-angled triangle, the same as the plain star triangle, so the loop skeleton is the familiar for i in 1..n, for j in 1..i.
  2. Content. The entries are consecutive integers that never reset. Row i therefore starts right after the total number of entries in rows 1 .. i-1, which is the triangular number T(i-1) = (i-1)i/2.

Those two observations lead to two different programs. The first keeps a running counter and never thinks about where a row starts. The second computes the starting number of each row directly from i, which makes every row independent of the ones before it and lets you answer “what is the 3rd number of row 100?” in constant time.

Both methods below return the whole picture as a single String with one row per line. This makes the output testable: main compares it to expected strings, checks structural properties for n up to 30, and only then prints it.

Approach 1: One running counter

Intuition. Treat the output as a single stream of integers 1, 2, 3, ... that is cut into rows of growing length. Keep one variable next, and every time you print a number, increment it. The nested loops only control the shape; the counter controls the content, and because it lives outside both loops it is never reset.

Algorithm.

  1. Set next = 1.
  2. For i from 1 to n:
  3. For j from 1 to i: if j > 1 append a space, then append next and increment it.
  4. End the row with a newline.
static String counter(int n) {
    StringBuilder sb = new StringBuilder();
    int next = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            if (j > 1) sb.append(' ');
            sb.append(next++);
        }
        sb.append('\n');
    }
    return sb.toString();
}

Complexity. Time O(n^2): there are n(n+1)/2 numbers, each appended in constant time (the number of digits is bounded by a small constant for any realistic n). Space O(n^2) for the returned string, which is the size of the output; only one extra int otherwise.

The if (j > 1) guard puts a separator between numbers rather than after each one, which avoids trailing spaces. Trailing whitespace is invisible but makes string comparisons in tests fail, so it is worth avoiding from the start.

Approach 2: Compute each row’s first number

Intuition. Rows 1 .. i-1 contain 1 + 2 + ... + (i-1) = i(i-1)/2 numbers. Row i therefore begins with i(i-1)/2 + 1 and continues for i steps. With that formula each row can be produced on its own, in any order, or even in parallel, and a single entry can be located without generating anything else.

Algorithm.

  1. For i from 1 to n: let first = i(i-1)/2 + 1.
  2. For j from 0 to i-1: if j > 0 append a space, then append first + j.
  3. End the row with a newline.
static String formula(int n) {
    StringBuilder sb = new StringBuilder();
    for (int i = 1; i <= n; i++) {
        long first = (long) i * (i - 1) / 2 + 1;   // T(i-1) + 1
        for (int j = 0; j < i; j++) {
            if (j > 0) sb.append(' ');
            sb.append(first + j);
        }
        sb.append('\n');
    }
    return sb.toString();
}

The same formula gives the value at any position directly:

static long valueAt(int r, int c) {
    return (long) r * (r - 1) / 2 + c;
}

valueAt(r, c) is the c-th number (1-based) of row r. For instance valueAt(4, 2) = 6 + 2 = 8, and indeed row 4 is 7 8 9 10.

Dry run for n = 5:

i T(i-1) first row
1 0 1 1
2 1 2 2 3
3 3 4 4 5 6
4 6 7 7 8 9 10
5 10 11 11 12 13 14 15

Complexity. Time O(n^2) to build the triangle, O(1) for valueAt. Space O(n^2) for the output string.

Why long? i * (i - 1) is computed before the division, and for i around 50 000 it already exceeds 2^31. Casting the first factor to long makes the whole product a long multiplication. The test valueAt(100000, 1) == 4999950001L would silently return a wrong value with int arithmetic. Note also that i(i-1) is always even, so the integer division is exact.

Edge cases and pitfalls