Solution: Strobogrammatic Number
Let’s solve the Strobogrammatic Number problem using the Two Pointers pattern.
We'll cover the following
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:
num.length
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
Now, let’s walk through the steps of the solution:
We initialize a map,
dict
, to store the valid mappings of digits that either remain the same or transform correctly when rotated 180 degrees:'0'
maps to'0'
'1'
maps to'1'
'8'
maps to'8'
'6'
maps to'9'
'9'
maps to'6'
We set two pointers:
left
starts at the beginning of the string.right
starts at the end of the string.
We iterate from both ends of the string using
left
andright
pointers toward the middle. In each iteration, we compare the pair of digits pointed byleft
andright
pointers. For each pair, we do the following:We check whether
num[left]
exists indict
. If not, we return FALSE because it is not a valid strobogrammatic digit. Otherwise, we retrieve the expected rotated value ofnum[left]
fromdict
. If this expected value does not matchnum[right]
pointer, we return FALSE because it means the number is not strobogrammatic.We increment the
left
pointer byand decrement the right
pointer by, moving toward the center of the string.
We keep iterating until the
left
pointer crosses theright
pointer.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.