Problem Description

You are given a string num that represents an integer. Your task is to determine if this number is a strobogrammatic number.

A strobogrammatic number is a number that looks exactly the same when you rotate it 180 degrees (turn it upside down).

To understand this better, think about which digits remain valid when rotated:

• 0 rotated 180° becomes 0
• 1 rotated 180° becomes 1
• 6 rotated 180° becomes 9
• 8 rotated 180° becomes 8
• 9 rotated 180° becomes 6
• Other digits like 2, 3, 4, 5, 7 don't form valid digits when rotated

For a number to be strobogrammatic, when you rotate the entire number 180 degrees:

1. Each digit must be rotatable to a valid digit
2. The resulting number must be identical to the original

For example:

• "69" is strobogrammatic because when rotated, 6 becomes 9 and 9 becomes 6, and the positions swap, giving us "69" again
• "88" is strobogrammatic because both 8s remain 8 after rotation
• "962" is not strobogrammatic because 2 cannot be rotated to form a valid digit

Return true if the given number is strobogrammatic, otherwise return false.

Intuition

When we rotate a number 180 degrees, two things happen simultaneously: each digit gets rotated individually, and the entire sequence gets reversed (what was on the left goes to the right and vice versa).

This means for a number to look the same after rotation, we need to check if the first digit when rotated equals the last digit, the second digit when rotated equals the second-to-last digit, and so on.

Think of it like checking if a word is a palindrome, but with an extra twist - instead of checking if characters are the same, we check if the rotated version of one character matches the other.

For instance, in "69":

• First digit 6 rotated gives 9, which should match the last digit (which is 9) ✓
• Last digit 9 rotated gives 6, which should match the first digit (which is 6) ✓

This naturally leads us to a two-pointer approach: start from both ends and work towards the middle, checking if each pair of digits satisfies the rotation relationship.

We can precompute the rotation mapping: 0→0, 1→1, 6→9, 8→8, 9→6, and mark invalid digits (like 2, 3, 4, 5, 7) as -1. Then for each pair of digits at positions i and j, we simply verify if rotate(num[i]) == num[j].

If we successfully check all pairs without finding a mismatch, the number is strobogrammatic.

Solution Approach

We implement the two-pointer approach using an array to store the rotation mappings.

First, we create an array d where the index represents a digit (0-9) and the value represents what that digit becomes after a 180° rotation:

• d[0] = 0 (0 rotates to 0)
• d[1] = 1 (1 rotates to 1)
• d[6] = 9 (6 rotates to 9)
• d[8] = 8 (8 rotates to 8)
• d[9] = 6 (9 rotates to 6)
• All other positions are set to -1 to indicate invalid rotations

The algorithm works as follows:

1. Initialize two pointers: i at the start (index 0) and j at the end (index len(num) - 1) of the string.

2. While i <= j:

   • Extract the digits at positions i and j: a = int(num[i]) and b = int(num[j])
   • Check if the rotation of digit a equals digit b by verifying if d[a] == b
   • If they don't match, immediately return False as the number cannot be strobogrammatic
   • Move the pointers inward: i = i + 1 and j = j - 1

3. If we complete the loop without returning False, all digit pairs satisfy the strobogrammatic property, so return True.

The key insight is that we're checking pairs from outside to inside. For a number like "69", we check if d[6] == 9 (which is true) and if d[9] == 6 (which is also true when the pointers meet or cross).

Time complexity: O(n) where n is the length of the string, as we traverse at most half the string. Space complexity: O(1) as we use a fixed-size array of 10 elements.

Example Walkthrough

Let's walk through the solution with the example num = "69".

Step 1: Initialize the rotation mapping array

d = [-1, 1, -1, -1, -1, -1, 9, -1, 8, 6]
     0   1   2   3   4   5   6   7   8   9  (indices/digits)

This array tells us: 0→0, 1→1, 6→9, 8→8, 9→6, and all other digits are invalid (marked as -1).

Step 2: Set up two pointers

• i = 0 (pointing to '6')
• j = 1 (pointing to '9')
• String: "69"
• Pointers: ↑ ↑ (i and j)

Step 3: First iteration (i=0, j=1)

• Extract digits: a = 6, b = 9
• Check rotation: d[6] = 9. Does 9 == 9? Yes! ✓
• Move pointers: i = 1, j = 0

Step 4: Check loop condition

• Is i <= j? Is 1 <= 0? No, so we exit the loop.

Step 5: Return result Since we successfully checked all pairs without finding a mismatch, return True.

Let's trace through one more example where the number is NOT strobogrammatic: num = "692".

Step 1: Same rotation mapping array as before

Step 2: Set up two pointers

• i = 0 (pointing to '6')
• j = 2 (pointing to '2')
• String: "692"
• Pointers: ↑ ↑ (i and j)

Step 3: First iteration (i=0, j=2)

• Extract digits: a = 6, b = 2
• Check rotation: d[6] = 9. Does 9 == 2? No! ✗
• Return False immediately

The algorithm correctly identifies that "692" is not strobogrammatic because the first digit '6' (which rotates to '9') doesn't match with the last digit '2'.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string num. The algorithm uses a two-pointer approach, with pointer i starting from the beginning and pointer j starting from the end of the string. In each iteration, both pointers move one step closer to each other (i increments and j decrements). The while loop continues as long as i <= j, which means it runs approximately n/2 times. Since we perform constant-time operations (array lookup and comparison) in each iteration, the total time complexity is O(n/2) which simplifies to O(n).

The space complexity is O(1). The algorithm uses a fixed-size array d of length 10 to store the strobogrammatic digit mappings, which takes constant space regardless of the input size. The only other variables used are the two pointers i and j, and temporary variables a and b for storing digit values, all of which require constant space. Therefore, the overall space complexity is O(1).

Common Pitfalls

Pitfall 1: Incorrect Rotation Mapping Logic

A common mistake is misunderstanding what "rotation" means in this context. Some developers might think that checking rotated_mapping[left_digit] == right_digit is sufficient, but forget that this relationship must be symmetric.

Incorrect approach:

# Only checking one direction
if rotated_mapping[left_digit] != right_digit:
    return False

Why it fails: Consider the string "60". Using only the above check:

• Left digit is 6, right digit is 0
• rotated_mapping[6] = 9, which doesn't equal 0
• Returns False (correct in this case)

But consider "90":

• Left digit is 9, right digit is 0
• rotated_mapping[9] = 6, which doesn't equal 0
• Returns False (correct)

However, the real issue appears with invalid digits. If we had "20":

• Left digit is 2, right digit is 0
• rotated_mapping[2] = -1, which doesn't equal 0
• Returns False (correct, but what if the right digit was also invalid?)

Better solution: Explicitly check that both digits are valid for rotation:

# Check if either digit cannot be rotated
if rotated_mapping[left_digit] == -1 or rotated_mapping[right_digit] == -1:
    return False

# Then check if they form a valid strobogrammatic pair
if rotated_mapping[left_digit] != right_digit:
    return False

Pitfall 2: Array Index Out of Bounds

Another mistake is not handling potential invalid input where the string might contain non-digit characters or digits outside the 0-9 range.

Problematic code:

left_digit = int(num[left_pointer])  # Assumes valid digit
right_digit = int(num[right_pointer])
if rotated_mapping[left_digit] != right_digit:  # Could cause IndexError
    return False

Solution: Add input validation:

# Validate that all characters are digits first
if not num.isdigit():
    return False

# Or handle during iteration
try:
    left_digit = int(num[left_pointer])
    right_digit = int(num[right_pointer])
    if left_digit > 9 or right_digit > 9:  # Additional safety check
        return False
except (ValueError, IndexError):
    return False

Pitfall 3: Misunderstanding Middle Element Requirements

For odd-length strings, there's a middle element that must rotate to itself. Some might forget to validate this special case.

Issue: When the pointers meet at the middle (left_pointer == right_pointer), we're checking if a digit equals its own rotation. Only 0, 1, and 8 satisfy this property.

Example: The string "696" has '9' in the middle. When rotated, 9 becomes 6, not 9, so it cannot be in the middle of a strobogrammatic number.

The current solution handles this correctly because when left_pointer == right_pointer:

# For middle element, we check rotated_mapping[digit] == digit
# This only works for 0, 1, and 8
if rotated_mapping[middle_digit] != middle_digit:
    return False

This automatically validates that only self-rotating digits (0, 1, 8) can be in the middle position.