☕ DSA Java Articles

Topics › Basics › Patterns

Pattern 18

Easy TUF ID 410 A2Z

Java source ↗ Edit this article ↗

Problem

Given a positive integer n, print the alpha-triangle: n rows that all end with the n-th capital letter. Row i (counting from 1) contains i letters, the last i letters of A .. (n-th letter), separated by single spaces. For n = 5 the rows are E, D E, C D E, B C D E, A B C D E.

Constraints: 1 ≤ n ≤ 26, because there are 26 letters.

Example 1

n = 3
C
B C
A B C

The right end is anchored at C; each row extends one letter further to the left.

Example 2

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

The last row is the full alphabet prefix of length n.

Reading the pattern

The shape is the usual growing triangle: row i has i entries. The content, however, is anchored on the right. Using 0-based letter indices (A = 0), row i runs from index n - i up to n - 1. Check: row 1 is just index n - 1 (the n-th letter), and row n is indices 0 .. n - 1, the whole prefix.

So, compared with the increasing letter triangle A / A B / A B C, only the start of the inner loop changes: it begins at n - i instead of 0. Getting comfortable with “same loop shape, shifted start” is the main skill this pattern trains.

A second view: every row is the previous row with one more letter glued on the front. If you keep the current row in a buffer and prepend the next letter (and a space), you never recompute anything. That is the mirror image of the “append one more letter” idea used in growing patterns.

Both approaches return the whole pattern as one String, one row per line, so main can compare them against fixed expectations and structural checks before printing.

Approach 1: Nested loops with a shifted start

Intuition. Outer loop over rows; inner loop over letter indices j from n - i to n - 1. Append a space before every letter except the first of the row, which is the one at j == n - i.

Algorithm.

  1. For i from 1 to n:
  2. For j from n - i to n - 1: if j > n - i 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 = n - i; j < n; j++) {
            if (j > n - i) sb.append(' ');
            sb.append((char) ('A' + j));
        }
        sb.append('\n');
    }
    return sb.toString();
}

Complexity. Time O(n^2): n(n+1)/2 letters and n(n-1)/2 spaces. Space O(n^2) for the output string, with constant extra memory.

Why (char) ('A' + j) and not 'A' + j? The sum of a char and an int is an int; append(int) would print numbers such as 69. The cast turns the code point back into a character.

Approach 2: Grow the row leftwards

Intuition. Row i is row i - 1 with the letter (char) ('A' + n - i) and a separating space placed in front. Keep the current row in a StringBuilder and use insert(0, ...) to prepend. Each row is then emitted with a single append.

Algorithm.

  1. Keep row = "".
  2. For i from 1 to n: let ch = (char) ('A' + n - i). If i > 1, insert a space at position 0. Insert ch at position 0.
  3. Append row and a newline.
static String growLeft(int n) {
    StringBuilder sb = new StringBuilder();
    StringBuilder row = new StringBuilder();
    for (int i = 1; i <= n; i++) {
        char ch = (char) ('A' + n - i);
        if (i > 1) row.insert(0, ' ');
        row.insert(0, ch);
        sb.append(row).append('\n');
    }
    return sb.toString();
}

Dry run for n = 4:

i ch row after prepending printed
1 D D D
2 C C D C D
3 B B C D B C D
4 A A B C D A B C D

Complexity. Time O(n^2): insert(0, ...) shifts the existing characters, which costs O(i) for row i, and copying the row into the output costs the same. Space O(n^2) for the output plus O(n) for the working row.

The order of the two inserts matters. Insert the space first and then the letter so that the letter ends up at index 0 and the space between it and the old content. Doing it the other way round yields " CD" with a leading space.

Edge cases and pitfalls