Strobogrammatic Number - Solution & Explanation

Problem Overview: A number is strobogrammatic if it appears the same when rotated 180 degrees. Digits like 0, 1, and 8 remain the same after rotation, while 6 becomes 9 and 9 becomes 6. Given a numeric string, verify whether the rotated version still forms the same number.

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

Create a rotation map for valid digit pairs: {0→0, 1→1, 6→9, 8→8, 9→6}. Iterate through the string from right to left, append the rotated counterpart for each digit, and build a new string. If a digit is not present in the mapping, the number cannot be strobogrammatic. After constructing the rotated string, compare it with the original. This approach is straightforward and clearly models the rotation process, but it uses extra memory to store the reversed representation.

The idea relies on constant-time lookups using a hash table. Each digit is validated and converted using the mapping. If the final constructed string equals the original input, the number remains unchanged after a 180° rotation. Time complexity is O(n) because every digit is processed once, while space complexity is O(n) for the auxiliary string.

Approach 2: Two Pointers Simulation (O(n) time, O(1) space)

Use two pointers starting at the leftmost and rightmost digits. For every step, verify that the left digit correctly rotates to the right digit using the same valid mapping. For example, if the left pointer is at 6, the right pointer must be 9. Move both pointers inward until they cross.

This works because a strobogrammatic number must be symmetric under rotation. Instead of constructing a new string, you validate each mirrored pair directly. A middle digit (when length is odd) must be one of 0, 1, or 8 since these rotate to themselves.

The two-pointer scan processes each pair once, giving O(n) time complexity. It stores only the mapping and pointer indices, so the space complexity is O(1). The pattern is a common application of two pointers combined with digit validation on a string.

Recommended for interviews: Interviewers usually expect the two-pointer simulation. The brute-force rotated-string approach shows that you understand the digit mapping, but the two-pointer method demonstrates stronger problem-solving by eliminating extra space and validating symmetry in one pass.