Strobogrammatic Number - Solution & Explanation

Problem Overview: A number is strobogrammatic if it appears the same after rotating it 180 degrees. Valid rotations are 0→0, 1→1, 8→8, 6→9, and 9→6. Given a numeric string, determine whether every digit pair still forms a valid number after this rotation.

Approach 1: Build Rotated String with Hash Map (O(n) time, O(n) space)

Create a mapping of valid rotations using a hash table: {0:0, 1:1, 8:8, 6:9, 9:6}. Iterate through the string from right to left, converting each digit using the map and building a rotated version. If any digit does not exist in the map (like 2 or 7), the number cannot be strobogrammatic. After constructing the rotated string, compare it with the original input. The algorithm scans the string once, giving O(n) time complexity, but uses O(n) extra space to store the rotated result.

Approach 2: Two Pointers with Rotation Map (O(n) time, O(1) space)

This approach validates pairs directly without building another string. Use a rotation map and place two pointers at the beginning and end of the string. At each step, check whether the left digit maps to the right digit using the rotation rules. For example, if the left pointer sees 6, the right pointer must be 9. Move both pointers inward until they meet. If all pairs match, the number is strobogrammatic. This approach performs a single pass and only stores the constant-size mapping, so it runs in O(n) time and O(1) space.

Approach 3: Center-Aware Validation (O(n) time, O(1) space)

A slight variation of the two-pointer method explicitly handles the middle digit when the string length is odd. Digits like 0, 1, and 8 remain valid when placed in the center after rotation. While scanning pairs with two pointers, the algorithm also checks the center position when left == right. If the center digit is not one of the self-rotating digits, the number is invalid. Complexity remains linear because each character is checked at most once.

Recommended for interviews: The two-pointer approach is the expected solution. It demonstrates that you understand digit rotation rules and can validate symmetric pairs efficiently without allocating extra memory. Showing the hash-map build approach first can help communicate the rotation logic, but interviewers usually want the O(n) time, O(1) space two-pointer solution.