Skip to main content

247. Strobogrammatic Number II

medium

Generate all strobogrammatic numbers of length n — numbers that look the same when rotated 180 degrees. The recursion builds outward from the center, two characters at a time, restricting choices to the strobogrammatic digit set.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an integer n, return all the strobogrammatic numbers that are of length n. You may return the answer in any order. A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Constraints

  • 1 <= n <= 14

Examples

Example 1

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

Example 2

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Strobogrammatic digit pairs: (0,0), (1,1), (6,9), (8,8), (9,6). Singletons: 0, 1, 8.

Hint 2

Recurse on a target inner length and the outer length. helper(k) returns all strobogrammatic strings of length k.

Hint 3

Base cases: k == 0 -> [""], k == 1 -> ["0", "1", "8"].

Hint 4

Recursive: for each inner string from helper(k - 2), wrap it with each pair. Skip outer (0, 0) when this isn't the innermost recursion (no leading zeros).

Solution approach

Reveal approach

Recurse on length: helper(k, isOuter). Base cases: k == 0 -> return [""]; k == 1 -> return ["0", "1", "8"]. Recursive: get inner strings from helper(k - 2, false), then for each pair in [('0','0'),('1','1'),('6','9'),('8','8'),('9','6')], if isOuter and pair == ('0','0'), skip (no leading zero in the final answer). Otherwise wrap inner with pair: pair[0] + inner + pair[1]. Top-level call: helper(n, true). Time and space are O(5^(n/2) * n) — the number of valid strobogrammatic numbers grows exponentially in n/2.

Complexity

Time
O(5^(n/2) * n)
Space
O(5^(n/2) * n)

Related patterns

  • recursion
  • build-from-center

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google
  • Meta

Practice these live with InterviewChamp.AI

Drill Strobogrammatic Number II and Recursion problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →