☕ DSA Java Articles

Topics › Basics › Patterns

Pattern 14

Easy TUF ID 406 A2Z

Java source ↗ Edit this article ↗

Problem

Given a positive integer n, print the increasing letter triangle: n rows where row i (counting from 1) contains the first i capital letters of the alphabet, A to the i-th letter, separated by single spaces.

Constraints: 1 ≤ n ≤ 26, since there are only 26 letters. The code does not crash for larger n, but the characters after Z are no longer letters.

Example 1

n = 3
A
A B
A B C

Every row starts over at A and goes one letter further than the row above.

Example 2

n = 5
A
A B
A B C
A B C D
A B C D E

The last row contains the first five letters.

Reading the pattern

This pattern is the letter version of the number pyramid 1 / 1 2 / 1 2 3. The shape is the usual right-angled triangle, for i in 1..n, for j in 0..i-1, and the content in column j (0-based) is the letter 'A' + j.

The one new ingredient is character arithmetic. In Java a char is a 16-bit unsigned integer holding a Unicode code point. 'A' is 65, 'B' is 66, and so on through 'Z' = 90. When you write 'A' + j, both operands are promoted to int and the result is an int; to append it as a letter you must cast it back with (char) ('A' + j). Without the cast, sb.append('A' + 2) appends the text "67", not C.

There is also a useful structural observation: every row is a prefix of the last row. Row i is simply the first 2i - 1 characters of A B C D E ... (i letters plus i - 1 spaces). That gives a second, different way to produce the output.

Both approaches return the pattern as one String with a newline after every row, so main can compare them against expected strings before printing.

Approach 1: Nested loops with char arithmetic

Intuition. Walk the triangle cell by cell. The row index decides how many letters to print; the column index decides which letter. Put a space before every letter except the first so that no row ends with trailing whitespace.

Algorithm.

  1. For i from 1 to n:
  2. For j from 0 to i - 1: if j > 0 append a space; append (char) ('A' + j).
  3. End the row with a newline.
static String nestedLoops(int n) {
    StringBuilder sb = new StringBuilder();
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            if (j > 0) sb.append(' ');
            sb.append((char) ('A' + j));
        }
        sb.append('\n');
    }
    return sb.toString();
}

Complexity. Time O(n^2): the triangle has n(n+1)/2 letters and almost as many spaces, each appended in O(1). Space O(n^2) for the output string; no other memory grows with n.

Approach 2: Every row is a prefix of the last row

Intuition. Build the longest row, A B C ... with n letters, exactly once. Then row i is that string cut after 2i - 1 characters: i letters interleaved with i - 1 spaces. StringBuilder.append(CharSequence, start, end) copies that range without creating an intermediate String.

This is a general trick for “growing” patterns whose rows share a common start: compute the largest row once and slice it.

Algorithm.

  1. Build full = the letters A .. (n-th letter) separated by spaces; its length is 2n - 1.
  2. For i from 1 to n: append full[0, 2i - 1) and a newline.
static String prefixOfLastRow(int n) {
    StringBuilder full = new StringBuilder();          // "A B C ... " with n letters
    for (int j = 0; j < n; j++) {
        if (j > 0) full.append(' ');
        full.append((char) ('A' + j));
    }
    StringBuilder sb = new StringBuilder();
    for (int i = 1; i <= n; i++) {
        sb.append(full, 0, 2 * i - 1).append('\n');   // i letters and i-1 spaces
    }
    return sb.toString();
}

Dry run for n = 4, where full = "A B C D" (length 7):

i prefix length 2i-1 row
1 1 A
2 3 A B
3 5 A B C
4 7 A B C D

Complexity. Time O(n^2): building full is O(n), and the copies total 1 + 3 + 5 + ... + (2n-1) = n^2 characters. Space O(n^2) for the output plus O(n) for full.

Why is the prefix length 2i - 1 and not 2i? Each letter except the last is followed by one space, so i letters use i + (i - 1) characters. If you used 2i you would copy the space after the last letter and reintroduce trailing whitespace.

Edge cases and pitfalls