Strobogrammatic number LeetCode

A strobogrammatic number is a number that appears the same when viewed upside down, that is when rotated by 180 degrees. For example, the numbers 0, 1, and 8 remain the same when rotated, while the number 6 becomes 9 and number 9 becomes 6. These numbers are significant in fields like digital displays and cryptography due to their unique symmetrical properties. This property is useful in designing systems where readability from different orientations is crucial.

Solution

To tackle this coding problem effectively, we will explore two potential solutions, each offering unique approaches and advantages.

Algorithm 1: Using a dictionary

The first step involves creating a dictionary that defines valid strobogrammatic pairs, such as (0, 0), (1, 1), (8, 8), (6, 9), and (9, 6). Then, two pointers are initialized—one at the beginning of the string and the other at the end. These pointers move toward each other, checking whether the characters they point to form a valid strobogrammatic pair, according to the dictionary. If at any point the characters do not match a valid pair, the string is deemed not strobogrammatic, and the algorithm returns False. However, if the pointers meet (or cross for an odd-length string) without encountering invalid pairs, the string is confirmed to be strobogrammatic, and the algorithm returns True. The steps of the algorithm are given below:

Initialize a dictionary pairs mapping valid strobogrammatic pairs like {‘0’: ‘0’, ‘1’: ‘1’, ‘8’: ‘8’, ‘6’: ‘9’, ‘9’: ‘6’}.
Set two pointers, left at the start and right at the end of number.
Iterate while left is less than or equal to right.
Check if the characters at left and right form a valid strobogrammatic pair according to pairs. If not, return False.
If the iteration completes without finding invalid pairs, return True, indicating number is strobogrammatic.

Let’s look at the illustrations below to better understand the solution.

def is_strobogrammatic(number):
        # Create a dictionary of valid strobogrammatic pairs
        pairs = {'0': '0', '1': '1', '8': '8', '6': '9', '9': '6'}
        # Initialize two pointers
        left, right = 0, len(number) - 1
        # Move pointers towards each other
        while left <= right:
            left_char, right_char = number[left], number[right]
            # Check if the characters form a valid pair
            if left_char not in pairs or pairs[left_char] != right_char:
                return False  # Not a strobogrammatic number
            # Move pointers
            left += 1
            right -= 1
        # If pointers meet (or cross for odd-length string), it's strobogrammatic
        return True
    
def main():
    test_cases = ["69", "818", "123", "88", "690"]
    i = 1
    for number in test_cases:
        print(i, ".\tnumber: ", number, sep ="")
        print("\n\tIs strobogrammatic?", is_strobogrammatic(number))
        print("-"*100)
        i+=1
main();

Strobogrammatic number: Using a dictionary

Now that we have explored one of the solutions for this LeetCode problem, let’s analyze its time and space complexity to understand how efficiently it scales with larger inputs.

Time complexity

The time complexity of the above solution is $O(n)$ , where $n$ is the total number of elements in the number. This is because the function checks each pair of characters from the start and end of the string toward the center.

Space complexity

The space complexity of the above solution is $O(1)$ because it uses a fixed-size dictionary and a constant amount of additional space regardless of the input size.

Algorithm 2: Create a rotated version

The algorithm constructs a rotated version of number by iterating through its characters in reverse order, replacing ‘6’ with ‘9’ and vice versa, and keeping ‘0’, ‘1’, and ‘8’ unchanged. If the resulting rotated string matches the original number, the algorithm returns True; otherwise, it returns False, indicating that the number is not strobogrammatic. The steps of the algorithm are given below.

Create an empty list called rotated_string_builder to store the characters of the rotated string.
Iterate through each character c in the input string number, starting from the last character and moving backward.
1. If c is ‘0’, ‘1’, or ‘8’, append c to rotated_string_builder.
2. If c is ‘6’, append ‘9’ to rotated_string_builder.
3. If c is ‘9’, append ‘6’ to rotated_string_builder.
4. If c is none of the above, return False immediately as it’s an invalid digit for a strobogrammatic number.
Join the characters in rotated_string_builder to create the rotated string rotated_string.
Compare rotated_string with the original string number. If they are equal, return True (indicating number is strobogrammatic). Otherwise, return False.

Let’s look at the illustrations below to better understand the solution.

def is_strobogrammatic(number):
    rotated_string_builder = []
    # Loop backwards through the string
    for c in number[::-1]:
        if c in ('0', '1', '8'):
            rotated_string_builder.append(c)
        elif c == '6':
            rotated_string_builder.append('9')
        elif c == '9':
            rotated_string_builder.append('6')
        else:  # Invalid digit
            return False
    rotated_string = ''.join(rotated_string_builder)
    return number == rotated_string
def main():
    test_cases = ["69", "818", "123", "88", "690"]
    i = 1
    for number in test_cases:
        print(i, ".\tnumber: ", number, sep ="")
        print("\n\tIs strobogrammatic?", is_strobogrammatic(number))
        print("-"*100)
        i+=1
main();

Strobogrammatic number: Create a rotated version

Let’s analyze the time and space complexity of this solution.

Time complexity

The time complexity of the above solution is also $O(n)$ , where $n$ is the total number of elements in the number because we are traversing the string in the reverse direction once.

Space complexity

The space complexity of the above solution is $O(n)$ where $n$ is the length of the number. This is due to the storage of the rotated_string_builder list.

Continue learning with Educative

This is only a single coding problem. If you want to explore more coding challenges that can help prepare you for interviews at major tech companies, consider exploring the following blogs by Educative:

Strobogrammatic number LeetCode

Problem statement

Knowledge test

Solution

Algorithm 1: Using a dictionary

Time complexity

Space complexity

Algorithm 2: Create a rotated version

Time complexity

Space complexity

Continue learning with Educative