☕ DSA Java Articles

Topics › Basics › Patterns

Pattern 17

Easy TUF ID 409 A2Z

Java source ↗ Edit this article ↗

Problem

Given a positive integer n, print the alpha-hill: n centred rows. Row i (counting from 1) climbs from A up to the i-th letter and then comes back down to A, giving 2i - 1 letters, and is pushed right by n - i spaces so that the peaks line up in the middle. Letters inside a row are not separated by spaces.

Constraints: 1 ≤ n ≤ 26. Trailing spaces at the end of a row are not printed.

Example 1

n = 3
  A
 ABA
ABCBA

Each row is a palindrome whose middle letter is the row’s letter.

Example 2

n = 5
    A
   ABA
  ABCBA
 ABCDCBA
ABCDEDCBA

Row i has n - i leading spaces and 2i - 1 letters, so every row is n + i - 1 characters wide.

Reading the pattern

Two independent ideas are layered here.

  1. Centring. A row with 2i - 1 letters needs n - i spaces on its left so that its centre lands in the same column as every other row’s centre. (The original pattern also prints n - i spaces on the right; they are invisible, and the code here leaves them out so the output can be compared exactly.)
  2. The up-and-down letters. Within the letter block, position c (0-based, 0 ≤ c ≤ 2i - 2) holds the letter whose alphabet index is (i - 1) - |c - (i - 1)|: the peak 'A' + i - 1 sits at the centre c = i - 1, and each step away from the centre lowers the letter by one.

There are at least three ways to turn idea 2 into code, and they illustrate three habits worth having: simulate a moving value, reuse and mirror a previously built piece, or compute each cell from a formula. The article shows all three; they produce identical strings, which main checks for every n up to 26.

Approach 1: One letter that climbs and then descends

Intuition. Walk the 2i - 1 columns with a char variable ch that starts at 'A'. After printing, increment it while you are before the centre and decrement it after. The centre is reached after i - 1 increments, so the rule is “increment while j < i, otherwise decrement” with j counting columns from 1.

Algorithm.

  1. For i from 1 to n: append n - i spaces.
  2. Set ch = 'A'. For j from 1 to 2i - 1: append ch; if j < i then ch++ else ch--.
  3. End the row with a newline.
static String twoPhase(int n) {
    StringBuilder sb = new StringBuilder();
    for (int i = 1; i <= n; i++) {
        for (int s = 0; s < n - i; s++) sb.append(' ');
        char ch = 'A';
        for (int j = 1; j <= 2 * i - 1; j++) {
            sb.append(ch);
            if (j < i) ch++; else ch--;     // climb for the first i-1 steps, then descend
        }
        sb.append('\n');
    }
    return sb.toString();
}

Complexity. Time O(n^2): row i costs (n - i) + (2i - 1) appends, and the sum over all rows is O(n^2). Space O(n^2) for the output string, nothing else that grows.

Note that ch++ on a char is legal and keeps the type char; the compound operators apply an implicit cast. ch = ch + 1 would not compile, because ch + 1 is an int.

Approach 2: Mirror the rising half

Intuition. The rising half of row i is A B ... X where X is the i-th letter, and it is exactly the rising half of row i - 1 plus one letter. Keep it in a StringBuilder called up that grows by one character per row. The falling half is up reversed with its first character (the peak, which must appear only once) removed. Then the row is spaces + up + down.

Algorithm.

  1. Keep up = "".
  2. For i from 1 to n: append (char) ('A' + i - 1) to up.
  3. Let down = reverse of up without its first character.
  4. Append n - i spaces, up, down, and a newline.
static String mirror(int n) {
    StringBuilder sb = new StringBuilder();
    StringBuilder up = new StringBuilder();            // grows by one letter per row
    for (int i = 1; i <= n; i++) {
        up.append((char) ('A' + i - 1));
        String down = new StringBuilder(up).reverse().substring(1);   // "X..BA" minus the peak X
        sb.append(" ".repeat(n - i)).append(up).append(down).append('\n');
    }
    return sb.toString();
}

Dry run for n = 4:

| i | up | reverse(up) | down | row | |—|—|—|—|—| | 1 | A | A | (empty) | ` A | | 2 | AB | BA | A | ABA | | 3 | ABC | CBA | BA | ABCBA | | 4 | ABCD | DCBA | CBA | ABCDCBA` |

Complexity. Time O(n^2): copying and reversing up costs O(i) per row. Space O(n^2) for the output plus O(n) for up and the temporary reversed copy.

new StringBuilder(up) makes a copy before reversing, so up itself is left intact for the next row. Reversing up in place and reversing it back would also work but is easy to forget.

Approach 3: Distance from the centre

Intuition. Forget about movement and compute each cell. In the letter block of row i, the centre index is centre = i - 1. A column c is dist = |c - centre| steps from the centre, and its letter is centre - dist steps above A. This is the closed form behind the other two approaches, and it generalises: any symmetric pattern can be described by distance from an axis.

Algorithm.

  1. For i from 1 to n: let centre = i - 1; append n - i spaces.
  2. For c from 0 to 2i - 2: append (char) ('A' + centre - |c - centre|).
  3. End the row with a newline.
static String formula(int n) {
    StringBuilder sb = new StringBuilder();
    for (int i = 1; i <= n; i++) {
        int centre = i - 1;                            // index of the peak within the 2i-1 letters
        for (int s = 0; s < n - i; s++) sb.append(' ');
        for (int c = 0; c < 2 * i - 1; c++) {
            int dist = Math.abs(c - centre);
            sb.append((char) ('A' + (centre - dist)));
        }
        sb.append('\n');
    }
    return sb.toString();
}

Complexity. Time O(n^2) and space O(n^2) for the output, with O(1) extra memory. Every cell is computed independently from (i, c).

Edge cases and pitfalls