We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Strobogrammatic Number

Number: 246

Difficulty: Easy

Paid? Yes

Companies: Meta, Uber, Google

Problem Description

Given a string num representing an integer, determine whether it is a strobogrammatic number. A strobogrammatic number is one that appears the same when rotated 180 degrees. For example, the number "69" becomes "96", which matches when reversed with proper mapping.

Key Insights

  • Use a mapping that defines the valid rotated counterparts for digits (e.g., '6' maps to '9').
  • Apply two pointers (one at the start and one at the end) to check corresponding digits.
  • Special cases include checking for digits that do not have a valid rotated counterpart.
  • Stop the iteration when the pointers meet or cross.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the input string. Space Complexity: O(1) since only a few constant-space variables are used.

Solution

We solve the problem by using a two-pointer approach combined with a hash table (dictionary) for the valid rotated digit mappings. The algorithm works by initializing two pointers, one at the beginning and one at the end of the string. At each step, we check if the left digit is in our mapping and if its mapped value matches the right digit. If they don't match, the number is not strobogrammatic and we return false immediately. If all corresponding digits match, we return true. This approach efficiently checks symmetry with respect to 180 degree rotation using constant space and linear time.

Code Solutions

# Python implementation for checking strobogrammatic number
def isStrobogrammatic(num: str) -> bool:
    # Mapping for valid strobogrammatic digit pairs
    mapping = {'0': '0', '1': '1', '6': '9', '8': '8', '9': '6'}
    left, right = 0, len(num) - 1

    # Use two pointers to compare digits from both ends
    while left <= right:
        # If left digit is not a valid strobogrammatic digit
        # or its mapped counterpart does not match the right digit, return False
        if num[left] not in mapping or mapping[num[left]] != num[right]:
            return False
        left += 1
        right -= 1
    return True

# Example usage:
print(isStrobogrammatic("69"))  # Output: True
print(isStrobogrammatic("962")) # Output: False
← Back to All Questions