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
Example 1 Case 1
- Input
n=2- Output
[11,88,69,96]
00 is excluded as a leading-zero number; output order is arbitrary.
Example 2 Case 2
- Input
n=1- Output
[0,1,8]
6 and 9 do not rotate into themselves at the center.
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.
Hints Optional
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
- Allocate a char array of length n.
- Save a String copy when left passes right.
- If left equals right, try only 0, 1 and 8, then return.
- Otherwise place each valid pair; reject 00 only at the outermost position.
- 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.
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

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.
-
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.
-
Fill 11 and enter the interior
Java operationnumber[left] = pair[0]; number[right] = pair[1];Statenumber = "11"; child left = 1, right = 0The child has crossed indices, which means every position has already been filled.
-
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.
-
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.
-
Use pairs that exchange under rotation
Java operationnumber[left] = pair[0]; number[right] = pair[1];Statefill/save "69", then "96"; four strings remain6 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.
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.