Solution: Strobogrammatic Number

Let’s solve the Strobogrammatic Number problem using the Two Pointers pattern.

Statement

Given a string num representing an integer, determine whether it is a strobogrammatic number. Return TRUE if the number is strobogrammatic or FALSE if it is not.

Note: A strobogrammatic number appears the same when rotated 180180180 degrees (viewed upside down). For example, “69” is strobogrammatic because it looks the same when flipped upside down, while “962” is not.

Constraints:

  • 1<=1 <= num.length <=50<= 50

  • num contains only digits.

  • num has no leading zeros except when the number itself is zero.

Solution

The solution uses a two pointer approach to determine whether a given string num is a strobogrammatic number by checking its digits from both ends toward the center. It uses a set of valid digit mappings that remain unchanged when rotated 180180 degrees or transform into each other when flipped (such as 0'0' to 0'0', 1'1' to 1'1', 8'8' to 8'8', 6'6' to 9'9', and 9'9' to 6'6'). The key idea is to verify that each digit on the left side of the string correctly matches its mirrored counterpart on the right side. This means checking if the digit at the start aligns correctly with the corresponding digit at the end when viewed upside down. If all such pairs match according to the defined mappings, the number is considered strobogrammatic.

Now, let’s walk through the steps of the solution:

  1. We initialize a map, dict, to store the valid mappings of digits that either remain the same or transform correctly when rotated 180 degrees:

    1. '0' maps to '0'

    2. '1' maps to '1'

    3. '8' maps to '8'

    4. '6' maps to '9'

    5. '9' maps to '6'

  2. We set two pointers:

    1. left starts at the beginning of the string.

    2. right starts at the end of the string.

  3. We iterate from both ends of the string using left and right pointers toward the middle. In each iteration, we compare the pair of digits pointed by left and right pointers. For each pair, we do the following:

    1. We check whether num[left] exists in dict. If not, we return FALSE because it is not a valid strobogrammatic digit. Otherwise, we retrieve the expected rotated value of num[left] from dict. If this expected value does not match num[right] pointer, we return FALSE because it means the number is not strobogrammatic.

    2. We increment the left pointer by 11 and decrement the right pointer by 11, moving toward the center of the string.

  4. We keep iterating until the left pointer crosses the right pointer.

  5. After iterating, if all pairs are valid according to the strobogrammatic rules, we return TRUE, indicating that the number is strobogrammatic.

Let’s look at the following illustration to get a better understanding of the solution:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.