LeetCode 246 - Strobogrammatic Number

The problem asks us to determine whether a given numeric string remains valid and unchanged when rotated 180 degrees. This property is called being "strobogrammatic". A strobogrammatic number is formed only by digits that still represent valid digits after rotation.

leetcodeeasyhash-tabletwo-pointersstring

LeetCode Problem 246

Difficulty: 🟢 Easy
Topics: Hash Table, Two Pointers, String

Solution

Problem Understanding

The problem asks us to determine whether a given numeric string remains valid and unchanged when rotated 180 degrees. This property is called being "strobogrammatic".

A strobogrammatic number is formed only by digits that still represent valid digits after rotation. The valid transformations are:

  • 0 -> 0
  • 1 -> 1
  • 6 -> 9
  • 8 -> 8
  • 9 -> 6

All other digits become invalid after rotation. For example, 2, 3, 4, 5, and 7 do not map to valid digits when rotated upside down.

The input is provided as a string instead of an integer because the operation is fundamentally character-based. We are not performing arithmetic, we are checking whether the sequence of digits transforms correctly under rotation.

The expected output is:

  • true if the rotated number matches the original number
  • false otherwise

The constraints are small, with a maximum length of 50 characters. This tells us that performance is not a major concern, but we should still aim for a clean and efficient solution. Since the input contains only digits and no invalid characters, we only need to validate rotational compatibility.

Several edge cases are important:

  • Single digit numbers like "0", "1", and "8" are valid because they map to themselves.
  • Single digits like "2" or "5" are invalid because they do not have valid rotations.
  • Numbers with odd lengths must have a center digit that maps to itself, meaning only 0, 1, or 8 are allowed in the middle.
  • Digits like 6 and 9 must appear in mirrored positions because they rotate into each other.

Approaches

Brute Force Approach

A brute force solution would simulate the full rotation process. We could reverse the string, then replace each digit with its rotated counterpart, and finally compare the transformed result with the original input.

For example:

  • Reverse "69" to get "96"

  • Rotate each digit:

  • 9 -> 6

  • 6 -> 9

  • Result becomes "69"

  • Since it matches the original string, the number is strobogrammatic.

This approach works because rotating a number upside down effectively reverses the order of digits while transforming each digit according to the rotation mapping.

However, this method requires constructing an entirely new string. Although the constraints are small, it uses unnecessary extra space and performs more work than needed.

Optimal Approach

The key observation is that we do not actually need to build the rotated number.

Instead, we can compare characters from both ends of the string using two pointers:

  • The left digit must rotate into the right digit.
  • The right digit must correspond correctly to the left digit.

For example:

  • In "69", the left digit 6 rotates into 9, which matches the right side.
  • In "88", both digits rotate into themselves.

This allows us to validate the number in a single pass without constructing a new string.

A hash map is ideal here because it provides constant time lookup for each digit's rotated counterpart.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Builds a rotated copy of the string
Optimal O(n) O(1) Uses two pointers and constant sized mapping

Algorithm Walkthrough

  1. Create a hash map that stores all valid strobogrammatic digit mappings.

The mapping is:

0 -> 0
1 -> 1
6 -> 9
8 -> 8
9 -> 6

This structure allows constant time verification of whether a digit has a valid rotated form. 2. Initialize two pointers.

  • left = 0
  • right = len(num) - 1

The left pointer starts at the beginning of the string, and the right pointer starts at the end. 3. Compare digits while left <= right.

At each step:

  • Check whether the left digit exists in the mapping.
  • If it does not exist, return False.
  • Otherwise, verify that the rotated value of the left digit equals the right digit.

This directly checks whether the current pair forms a valid strobogrammatic relationship. 4. Move both pointers inward.

  • Increment left
  • Decrement right

Continue until all pairs have been checked. 5. If all comparisons succeed, return True.

This means every digit pair satisfies the rotational property.

Why it works

The algorithm relies on the defining property of strobogrammatic numbers: each digit on the left side must rotate into the corresponding digit on the right side.

By checking mirrored positions simultaneously, we guarantee that the entire number remains unchanged after a 180 degree rotation. Since every pair is validated independently and all valid rotations are covered by the mapping, the algorithm correctly determines whether the number is strobogrammatic.

Python Solution

class Solution:
    def isStrobogrammatic(self, num: str) -> bool:
        rotation_map = {
            '0': '0',
            '1': '1',
            '6': '9',
            '8': '8',
            '9': '6'
        }

        left = 0
        right = len(num) - 1

        while left <= right:
            left_digit = num[left]
            right_digit = num[right]

            if left_digit not in rotation_map:
                return False

            if rotation_map[left_digit] != right_digit:
                return False

            left += 1
            right -= 1

        return True

The implementation begins by defining the valid rotation relationships in a dictionary. This allows constant time lookup for each digit's rotated counterpart.

Two pointers are then initialized to scan inward from both ends of the string. At every iteration, the algorithm checks whether the current left digit can rotate into the current right digit.

If a digit is invalid or the rotated mapping does not match the opposite side, the function immediately returns False.

If all mirrored pairs satisfy the condition, the loop completes and the function returns True.

This implementation closely follows the mathematical definition of a strobogrammatic number and avoids unnecessary string construction.

Go Solution

func isStrobogrammatic(num string) bool {
    rotationMap := map[byte]byte{
        '0': '0',
        '1': '1',
        '6': '9',
        '8': '8',
        '9': '6',
    }

    left := 0
    right := len(num) - 1

    for left <= right {
        leftDigit := num[left]
        rightDigit := num[right]

        rotatedDigit, exists := rotationMap[leftDigit]

        if !exists {
            return false
        }

        if rotatedDigit != rightDigit {
            return false
        }

        left++
        right--
    }

    return true
}

The Go implementation follows the same logic as the Python version. The main difference is that Go strings are indexed as bytes, so the hash map uses byte keys and values instead of strings.

Go also requires explicit handling of map lookups using the exists boolean to determine whether a key is present.

Since the input length is very small, there are no concerns about memory usage or overflow.

Worked Examples

Example 1

Input:

num = "69"

Initial state:

Variable Value
left 0
right 1

Iteration 1:

Left Digit Right Digit Rotated Left Digit Match
6 9 9 Yes

Pointers move inward:

Variable Value
left 1
right 0

Loop ends because left > right.

Return True.

Example 2

Input:

num = "88"

Iteration 1:

Left Digit Right Digit Rotated Left Digit Match
8 8 8 Yes

Pointers move inward and loop terminates.

Return True.

Example 3

Input:

num = "962"

Iteration 1:

Left Digit Right Digit Rotated Left Digit Match
9 2 6 No

Since the rotated value does not match the right digit, return False.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each digit is checked at most once
Space O(1) The rotation map contains a fixed number of entries

The algorithm processes the string using two pointers that move toward the center. Each iteration performs constant time work, resulting in linear time complexity.

The extra space usage is constant because the hash map always contains exactly five mappings regardless of input size.

Test Cases

solution = Solution()

assert solution.isStrobogrammatic("69") == True      # basic valid pair
assert solution.isStrobogrammatic("88") == True      # symmetric valid digits
assert solution.isStrobogrammatic("962") == False    # invalid rotation

assert solution.isStrobogrammatic("0") == True       # single valid digit
assert solution.isStrobogrammatic("1") == True       # single valid digit
assert solution.isStrobogrammatic("8") == True       # single valid digit

assert solution.isStrobogrammatic("2") == False      # invalid single digit
assert solution.isStrobogrammatic("5") == False      # invalid single digit

assert solution.isStrobogrammatic("11") == True      # identical valid digits
assert solution.isStrobogrammatic("96") == True      # reversed valid pair
assert solution.isStrobogrammatic("818") == True     # odd length valid case
assert solution.isStrobogrammatic("619") == True     # mixed valid digits

assert solution.isStrobogrammatic("101") == True     # valid center digit
assert solution.isStrobogrammatic("609") == True     # 6 and 9 pairing

assert solution.isStrobogrammatic("916") == False    # incorrect mirrored pair
assert solution.isStrobogrammatic("123") == False    # contains invalid digits
assert solution.isStrobogrammatic("686") == False    # center mismatch
Test Why
"69" Standard valid strobogrammatic pair
"88" Self-rotating digits
"962" Invalid mirrored relationship
"0" Smallest valid input
"2" Invalid standalone digit
"818" Odd length valid number
"609" Valid use of 6 and 9
"916" Incorrect mirrored order
"123" Contains unsupported digits
"686" Incorrect center behavior

Edge Cases

One important edge case is a single digit input. Only 0, 1, and 8 remain valid after rotation because they map to themselves. Digits like 6 and 9 cannot appear alone because rotating them changes the digit. The implementation handles this naturally because the left and right pointers meet at the same index, and the mapping check ensures the digit maps to itself.

Another important case is odd length numbers. In these inputs, the middle digit has no mirrored partner, so it must be self-rotating. For example, "818" is valid because the center digit is 1, while "696" is invalid because the center digit 9 rotates into 6. The condition left <= right ensures the middle digit is checked correctly.

A third edge case involves invalid digits such as 2, 3, 4, 5, and 7. These digits have no valid rotated representation. A naive implementation might forget to reject them explicitly. This solution avoids that issue by checking whether each digit exists in the rotation map before attempting comparison. If a digit is absent, the function immediately returns False.