Watch 10 video solutions for Strobogrammatic Number, a easy level problem involving Hash Table, Two Pointers, String. This walkthrough by happygirlzt has 8,379 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given a string num which represents an integer, return true if num is a strobogrammatic number.
A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).
Example 1:
Input: num = "69" Output: true
Example 2:
Input: num = "88" Output: true
Example 3:
Input: num = "962" Output: false
Constraints:
1 <= num.length <= 50num consists of only digits.num does not contain any leading zeros except for zero itself.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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Build Rotated String with Hash Map | O(n) | O(n) | When clarity is preferred and constructing the rotated number helps visualize the transformation |
| Two Pointers Simulation | O(n) | O(1) | Best approach for interviews; validates mirrored digits directly without extra memory |