Code Implementation

class Solution:
    def isStrobogrammatic(self, num: str) -> bool:
        mapping = {'0': '0', '1': '1', '6': '9', '8': '8', '9': '6'}
        left, right = 0, len(num) - 1
        while left <= right:
            if num[left] not in mapping or num[right] not in mapping:
                return False
            if mapping[num[left]] != num[right]:
                return False
            left += 1
            right -= 1
        return True
      

class Solution {
public:
    bool isStrobogrammatic(string num) {
        unordered_map<char, char> mapping = {
            {'0', '0'}, {'1', '1'}, {'6', '9'}, {'8', '8'}, {'9', '6'}
        };
        int left = 0, right = num.size() - 1;
        while (left <= right) {
            if (mapping.find(num[left]) == mapping.end() || 
                mapping.find(num[right]) == mapping.end())
                return false;
            if (mapping[num[left]] != num[right])
                return false;
            left++;
            right--;
        }
        return true;
    }
};
      

class Solution {
    public boolean isStrobogrammatic(String num) {
        Map<Character, Character> map = new HashMap<>();
        map.put('0', '0');
        map.put('1', '1');
        map.put('6', '9');
        map.put('8', '8');
        map.put('9', '6');
        int left = 0, right = num.length() - 1;
        while (left <= right) {
            char l = num.charAt(left);
            char r = num.charAt(right);
            if (!map.containsKey(l) || !map.containsKey(r)) return false;
            if (map.get(l) != r) return false;
            left++;
            right--;
        }
        return true;
    }
}
      

/**
 * @param {string} num
 * @return {boolean}
 */
var isStrobogrammatic = function(num) {
    const map = {'0':'0', '1':'1', '6':'9', '8':'8', '9':'6'};
    let left = 0, right = num.length - 1;
    while (left <= right) {
        if (!(num[left] in map) || !(num[right] in map)) return false;
        if (map[num[left]] !== num[right]) return false;
        left++;
        right--;
    }
    return true;
};
      

Problem Description

You are given a string num representing a number. A strobogrammatic number is a number that looks the same when rotated 180 degrees (turned upside down). Return true if num is strobogrammatic, and false otherwise.

• Each digit must transform into a valid digit after rotation.
• The valid pairs are: 0 <-> 0, 1 <-> 1, 6 <-> 9, 8 <-> 8, 9 <-> 6.
• Other digits (such as 2, 3, 4, 5, 7) are not valid in any position.
• The function should check the entire string and return true only if the whole number is strobogrammatic.

Thought Process

At first glance, you might think to just reverse the string and check if it is the same as the original. However, strobogrammatic numbers are not palindromes. Instead, each digit must be replaced with its strobogrammatic counterpart and the string reversed.

The naive approach is to rotate the entire number, one digit at a time, and see if the result matches the original number. But we can optimize this by comparing matching pairs from the outside in, using two pointers. If any pair does not match the strobogrammatic mapping, we can return false early.

This approach minimizes unnecessary work and avoids extra space for building a new string.

Solution Approach

• Define a mapping: Create a dictionary (or map) that specifies which digits are strobogrammatic pairs: { '0':'0', '1':'1', '6':'9', '8':'8', '9':'6' }.
• Use two pointers: Set left at the start of the string and right at the end.
• Check pairs: For each iteration, check if num[left] and num[right] are both valid strobogrammatic digits. If not, return false.
• Compare mapping: Ensure that mapping[num[left]] == num[right]. If not, return false.
• Move inward: Increment left and decrement right until they cross.
• Return true: If all pairs match, the number is strobogrammatic.

This approach is efficient because it only checks each digit once and stops as soon as a mismatch is found.

Example Walkthrough

Let's walk through the example num = "619":

1. First iteration: left = 0 ('6'), right = 2 ('9'). The mapping for '6' is '9', which matches num[2].
2. Second iteration: left = 1 ('1'), right = 1 ('1'). The mapping for '1' is '1', which matches num[1].
3. Pointers cross: left = 2, right = 0. Loop ends. All pairs matched.

The function returns true because "619" is strobogrammatic.

If we try num = "962":

• left = 0 ('9'), right = 2 ('2'). '2' is not in the mapping, so we immediately return false.

Time and Space Complexity

• Brute-force approach: Build a rotated string by mapping each digit and reversing. Time: O(n), Space: O(n).
• Optimized two-pointer approach (our solution): Time: O(n), since each digit is checked once. Space: O(1), since we use only a fixed-size map and two pointers.

The optimized approach is preferred because it avoids building new strings and uses constant extra space.

Summary

To determine if a number is strobogrammatic, we check if each digit and its corresponding digit from the other end form a valid strobogrammatic pair. By using a two-pointer technique and a simple mapping, we efficiently solve the problem in linear time and constant space. The elegance of the solution lies in its directness and early exit on failure, making it both simple and optimal.