Find a lesson, question or project

Start typing to search published content and planned structures.

↑ ↓ moveEnter openEsc close

Strobogrammatic Number II in Java: Fill Matching Ends

Generate upside-down-symmetric numbers by filling two ends together, handling leading zero and odd centers, with code and a visual dry run.

MediumRecursion and backtrackingPattern: recursion, backtracking, two pointers

Problem statement

Generate all length-n numbers that look unchanged when rotated 180 degrees. Return strings, because the task concerns fixed-length digit arrangements rather than arithmetic.

Valid paired digits are 00, 11, 88, 69 and 96. Rotation reverses positions and changes each digit. For example, 69 rotates into 69; 66 rotates into 99 and is not valid.

No multi-digit number may begin with zero. The single digit zero is valid. Any output order is accepted. The supplied page does not expose a numeric n bound, so none is invented here. LeetCode Strobogrammatic Number II may require Premium.

Constraints & requirements

CONTRACT
Use pairs 00, 11, 88, 69 and 96. The center of an odd-length number permits only 0, 1 or 8. Any answer order is accepted. LeetCode may require Premium.

Examples 3 test cases

  1. Example 1 Case 1

    Input
    n=2
    Output
    [11,88,69,96]

    00 is excluded as a leading-zero number; output order is arbitrary.

  2. Example 2 Case 2

    Input
    n=1
    Output
    [0,1,8]

    6 and 9 do not rotate into themselves at the center.

  3. Example 3 Case 3

    Input
    n=3
    Output
    [101,111,181,808,818,888,609,619,689,906,916,986]

    Four outer pairs times three center choices give twelve numbers.

Solve on LeetCode ↗

Hints Optional

Hints become more specific one step at a time.
01Hint 1

Rotation exchanges the left and right positions.

02Hint 2

Place a compatible pair, then recurse inward.

03Hint 3

Treat an odd center separately and forbid 00 only at the outermost pair.

How to think before coding

A left digit forces its right partner: 0↔0, 1↔1, 8↔8, 6↔9. The state is the next unfilled left/right positions. Skip an outer leading zero only on multi-digit numbers. When the positions meet, allow only 0,1,8; when they cross, snapshot the buffer. Siblings overwrite owned positions, so no separate list-removal undo is required.

Brute force and the improvement

Enumerate all canonical length-n digit strings and rotate each one to test equality. There are O(10^n) candidates and each rotation costs O(n), giving O(n·10^n) time and O(n) candidate space, excluding output. Use strings rather than assuming every candidate fits an int. The improved method chooses compatible outer pairs together, so every completed candidate is already rotation-symmetric. This reduces useless generation; writing the returned strings still costs at least their total length.

Intuition: fill the ends together

For a three-digit number, picking 6 on the left forces 9 on the right. Only the center remains free, and it must rotate into itself: 0, 1 or 8. This branch gives 609, 619 and 689.

Filling arbitrary digits and checking afterward wastes most of the search. Instead, maintain a char array and fill compatible pairs from the outside inward. The state is (left,right), the next two unfilled positions.

Algorithm

  1. Allocate a char array of length n.
  2. Save a String copy when left passes right.
  3. If left equals right, try only 0, 1 and 8, then return.
  4. Otherwise place each valid pair; reject 00 only at the outermost position.
  5. Recurse with left+1 and right−1.

Java solution

The buffer stores fixed positions; each call fills matching ends or a valid center. The pair order does not promise numerically sorted output.

Java
import java.util.*;

class Solution {
    public static List<String> findStrobogrammatic(int n) {
        List<String> result = new ArrayList<>();
        fillRotated(new char[n], 0, n - 1, result); // Build mirrored positions together.
        return result; // Any output order is accepted; strings preserve fixed length.
    }
    private static void fillRotated(char[] number, int left, int right, List<String> result) {
        if (left > right) { // All positions are filled.
            result.add(new String(number)); // Snapshot before the buffer is reused.
            return;
        }
        if (left == right) { // The center must rotate into ITSELF, not its partner.
            for (char middle : new char[]{'0', '1', '8'}) {
                number[left] = middle;
                fillRotated(number, left + 1, right - 1, result);
            }
            return; // Do not also execute the two-position pair loop for the center.
        }
        for (char[] pair : new char[][]{{'0','0'}, {'1','1'}, {'8','8'}, {'6','9'}, {'9','6'}}) {
            if (left == 0 && pair[0] == '0') continue; // No leading zero in a multi-digit number.
            number[left] = pair[0]; number[right] = pair[1]; // Rotation exchanges these positions.
            fillRotated(number, left + 1, right - 1, result); // Fill the smaller inner region.
        }
    }

    public static void main(String[] args) {
        System.out.println(findStrobogrammatic(2)); // [11, 88, 69, 96] (any order)
    }
}

For n=2 this prints [11,88,69,96]. [11,69,88,96] is equally valid. The code takes positive n as the task assumption; it does not invent meaning for negative lengths.

Recursion branches and dry run

Numbered illustrated dry run for Strobogrammatic Number II; the text transcript explains the states.
Follow the numbered panels in order. Open full-size dry run ↗
Read the text transcript

Follow the Java, step by step

Example: n = 2

What to track: Track left, right and the shared char buffer. Each pair overwrites both positions; each saved String is independent. This is the complete two-digit generation.

  1. Reject the leading-zero pair

    Java operationif (left == 0 && pair[0] == '0') continue;
    Stateleft = 0; right = 1; pair = 00; result = []

    A two-digit number cannot start with zero. No child is created for 00.

  2. Fill 11 and enter the interior

    Java operationnumber[left] = pair[0]; number[right] = pair[1];
    Statenumber = "11"; child left = 1, right = 0

    The child has crossed indices, which means every position has already been filled.

  3. Save the first completed buffer

    Java operationresult.add(new String(number));
    Stateresult = ["11"]

    The copy is saved before the same buffer is reused for another pair.

  4. Overwrite with the next pair

    Java operationfillRotated(number, left + 1, right - 1, result);
    Stateparent fills "88"; its child saves it; result = ["11","88"]

    Every sibling overwrites both of its owned positions. A remove operation is unnecessary for this buffer strategy.

  5. Use pairs that exchange under rotation

    Java operationnumber[left] = pair[0]; number[right] = pair[1];
    Statefill/save "69", then "96"; four strings remain

    6 on the left requires 9 on the right, and vice versa. For an odd center the code uses only 0, 1 and 8 instead.

Final result: ["11","88","69","96"] in this traversal order.

Worked example · read from top to bottom
n=3: _ _ _
├─ outer 11 → 1 _ 1 → 101, 111, 181
├─ outer 88 → 8 _ 8 → 808, 818, 888
├─ outer 69 → 6 _ 9 → 609, 619, 689
└─ outer 96 → 9 _ 6 → 906, 916, 986
outer 00 → blocked: leading zero

After the child for 609 returns, the center call still has left=right=1. It overwrites position 1 with 1, then 8. Explicit clearing is unnecessary: each sibling overwrites the positions it owns, and each deeper call fills its entire interior before saving. The saved String is independent of the reusable buffer.

Why it works

Every chosen pair agrees under rotation, so all already-filled positions are compatible. An odd center uses only self-rotating digits. Every valid number is made of exactly these pairs plus its optional center; its choices are therefore visited. Each sequence of pairs has a unique digit string. Forbidding the outer zero pair removes invalid leading-zero representations without banning inner zeros.

Complexity and alternative approaches

For n≥2, let k=floor(n/2). There are 4·5^(k−1) outputs for even n, and three times that many for odd n. For n=1 there are three.

If P is that output count, generation and copying cost O(n·P), with O(n) buffer/call-stack space and O(n·P) output space. Checking every n-digit number instead examines roughly 10^n candidates and performs O(n) checks on each.

An inside-out recursive approach starts with the empty string for an even center or 0/1/8 for an odd center, then wraps compatible pairs around it. It is also correct, but must carefully distinguish outer from inner zero pairs.

Common mistakes

  • Treating 6 or 9 as valid standalone centers.
  • Allowing 00 at the outermost pair for n>1.
  • Rejecting inner zeros, which loses 1001 and 609.
  • Saving a reference to a mutable char buffer instead of a String snapshot.
  • Describing this as ordinary palindrome generation: 69 is rotation-symmetric but not a palindrome.

Practice next

Next lessonStrobogrammatic Number III

Back to Recursion and backtracking →