LeetCode 246: Strobogrammatic Number - All Solutions Explained

Problem Statement

The Strobogrammatic Number problem (LeetCode 246) asks you to determine if a given number looks the same when rotated 180 degrees (upside down). A strobogrammatic number is a number that appears the same when viewed upside down using only digits that form valid upside-down representations.

Valid Strobogrammatic Digits

• 0 → 0
• 1 → 1
• 6 → 9
• 8 → 8
• 9 → 6

Copy codeInput: num = "69"
Output: true

Input: num = "88"
Output: true

Input: num = "962"
Output: false

Solution 1: Two Pointers with Mapping (Best Solution)

Explanation of the Best Solution

This approach uses two pointers to compare digits from both ends while checking against a strobogrammatic mapping:

1. Create mapping dictionary: {digit: rotated_digit}
2. Initialize pointers: left = 0, right = len(num)-1
3. Check pairs:
4. While left ≤ right:
   • If num[left] not in mapping → false
   • If mapping[num[left]] ≠ num[right] → false
   • Move pointers inward
5. Return true if all checks pass

Step-by-Step Example

For num = "69": 1. left=0 ('6'), right=1 ('9') 2. mapping['6'] = '9' matches '9' → continue 3. left > right → true

For num = "962": 1. left=0 ('9'), right=2 ('2') 2. '2' not in mapping → false

Python Code (Two Pointers)

Copy codedef isStrobogrammatic(num: str) -> bool:
    mapping = {'0':'0', '1':'1', '6':'9', '8':'8', '9':'6'}
    left, right = 0, len(num)-1

    while left <= right:
        if num[left] not in mapping or mapping[num[left]] != num[right]:
            return False
        left += 1
        right -= 1

    return True

Complexity

• Time Complexity: O(n) - single pass through half the string
• Space Complexity: O(1) - constant space for mapping

Why It's the Best

• Most efficient solution
• Early termination on invalid digits
• Clear and concise
• Preferred in coding interviews

Solution 2: String Reversal with Translation

Explanation

This approach creates the rotated version and compares it to the original:

1. Create mapping dictionary
2. Build rotated string:
3. Replace each digit with its rotated version
4. Reverse the string
5. Compare with original

Python Code (String Reversal)

Copy codedef isStrobogrammatic(num: str) -> bool:
    mapping = {'0':'0', '1':'1', '6':'9', '8':'8', '9':'6'}
    rotated = []

    for char in reversed(num):
        if char not in mapping:
            return False
        rotated.append(mapping[char])

    return ''.join(rotated) == num

Complexity

• Time Complexity: O(n) - full string traversal
• Space Complexity: O(n) - stores rotated string

Pros and Cons

• Pros: Straightforward logic
• Cons: Uses extra space for rotated string

Solution 3: Recursive Construction (For Generation)

Explanation

This advanced solution demonstrates how to generate strobogrammatic numbers by recursively building valid combinations:

1. Base cases: Handle even/odd length centers
2. Recursive cases:
3. Add valid digit pairs to both ends
4. Build from center outward

Python Code (Recursive Generation)

Copy codedef findStrobogrammatic(n: int) -> List[str]:
    return helper(n, n)

def helper(n, length):
    if n == 0:
        return [""]
    if n == 1:
        return ["0", "1", "8"]

    middles = helper(n-2, length)
    result = []
    for middle in middles:
        if n != length:
            result.append("0" + middle + "0")
        result.append("1" + middle + "1")
        result.append("6" + middle + "9")
        result.append("8" + middle + "8")
        result.append("9" + middle + "6")
    return result

Complexity

• Time Complexity: O(5^(n/2)) - exponential growth
• Space Complexity: O(n) - recursion depth

When to Use

• When generating all strobogrammatic numbers
• Not for simple validation

Edge Cases to Consider

• Single digit numbers ("0", "1", "8")
• Even length numbers ("69", "88")
• Numbers with invalid digits ("123", "789")
• Large numbers (50 digits)
• Numbers with leading zeros (invalid per constraints)

Final Thoughts

• Two Pointers: Best for validation
• String Reversal: Alternative clear approach
• Recursive: For generation problems

For coding interviews, the two pointer solution is strongly recommended as it demonstrates optimal validation.