246. Strobogrammatic Number
Problem Description
The problem requires us to determine if a given string num
represents a strobogrammatic number. A strobogrammatic number is one that appears the same when flipped 180 degrees. Imagine looking at certain numbers on a digital clock; when rotated upside down, they still read as valid numbers. Notably, '6' becomes '9', '9' becomes '6', '8' remains '8', '1' remains '1', and '0' remains '0'. Numbers like '2', '3', '4', '5', and '7' do not form valid numbers when flipped, so they cannot be part of a strobogrammatic number.
The goal is to return true
if the number represented by the string num
is strobogrammatic and false
otherwise. It is important to consider how the number looks when each of its digits is rotated, and the entire string needs to be a valid number after the rotation.
Intuition
To determine if a number is strobogrammatic, we can map each digit to its corresponding digit when flipped 180 degrees. We initialize a list, d
, where the index corresponds to a digit and the value at that index corresponds to what the digit would look like after being flipped 180 degrees. In the list d
, a value of -1
means the digit does not form a valid number when flipped (these are the numbers that cannot contribute to a strobogrammatic number).
A strobogrammatic number should be symmetrical around its center. Therefore, we only need to compare the first half of the string to the second half. We set up two pointers, i
starting at the beginning of the string and j
at the end, and move them towards the center. At each step we:
- Convert the digits at indices
i
andj
to integersa
andb
. - Check whether the strobogrammatic counterpart of
a
is equal tob
. If it's not, we immediately returnfalse
since the number is not strobogrammatic. - Move the pointers inward,
i
going up andj
going down.
If we successfully traverse the string without mismatches, then the number is strobogrammatic and we return true
.
The solution is elegant because it only requires a single pass, giving us an efficient way to solve the problem with O(n) complexity, where n is the length of the string num
.
Learn more about Two Pointers patterns.
Solution Approach
The provided Python implementation uses a simple approach leveraging a list to check for strobogrammatic pairs and two-pointer technique to validate symmetry.
Below is a step-by-step explanation of the algorithm:
-
Data Structure: We use a list called
d
where each indexi
corresponds to the digit i in integer form, and the value atd[i]
represents what the digit would look like if flipped 180 degrees. For digits that are invalid upon flipping (2, 3, 4, 5, 7), we assign a value of-1
. -
Two-Pointer Technique: To validate that the
num
is strobogrammatic, we use two pointers,i
andj
. The pointeri
starts at the beginning of the stringnum
(index 0), andj
starts at the end of the string (indexlen(num) - 1
). -
Iteration and Validation: The algorithm iterates over the string by moving
i
from the start toward the end, andj
from the end toward the start. At each iteration, it:- Converts characters at current indices
i
andj
to integersa
andb
, respectively. - Uses
d[a]
to obtain the flipped counterpart ofa
. - If
d[a]
does not equalb
, thennum
cannot be strobogrammatic, hence the function returnsfalse
.
- Converts characters at current indices
-
Termination Condition: The iteration stops when the pointers
i
andj
meet or cross each other (i > j
), indicating the entire string has been checked. -
Returning the Result: If the function hasn't returned
false
by the end of the iteration, it meansnum
is strobogrammatic and the function returnstrue
.
This algorithm employs an array to emulate a direct mapping, which offers an efficient lookup time of O(1) for each digit's strobogrammatic counterpart, and it runs in linear time relative to the length of the string num
, resulting in O(n) time complexity. The space complexity is constant O(1), only requiring storage for the list d
, which has a fixed length of 10, and the two index variables i
and j
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach using a small example where num
is "69"
. We want to determine if this string represents a strobogrammatic number.
-
Data Structure Initialization: According to the algorithm, we set up a list
d
mapping digits to their flipped counterparts:1d = [-1, 1, -1, -1, -1, -1, 9, -1, 8, 6]
-
Initializing Pointers: We have two pointers
i
andj
. In our case,i
starts at index0
andj
starts at index1
(since the string"69"
has a length of 2). -
Iteration and Validation:
- For the first iteration (
i = 0
,j = 1
):- We convert the character at index
i
to an integera
(a = 6
). - We convert the character at index
j
to an integerb
(b = 9
). - We then use
d[a]
to find the flipped counterpart ofa
(d[6] = 9
). - We check if
d[a]
equalsb
. In this case,d[6]
(which is9
) is equal tob
(which is also9
), so we proceed.
- We convert the character at index
- We then move the pointers inward:
i
goes up to1
andj
goes down to0
. - Since
i
now meetsj
, our loop terminates.
- For the first iteration (
-
Termination Condition:
- The pointers
i
andj
have met, indicating we've checked all necessary digits.
- The pointers
-
Returning the Result:
- Since there were no mismatches during the iteration, we conclude that the string
"69"
is strobogrammatic. - The function would return
true
.
- Since there were no mismatches during the iteration, we conclude that the string
By following this procedure with the given example, we demonstrate how the algorithm successfully identifies that the string "69"
is a strobogrammatic number using the two-pointer technique and a fixed mapping list for valid strobogrammatic pairs.
Solution Implementation
1class Solution:
2 def isStrobogrammatic(self, num: str) -> bool:
3 # Mapping of strobogrammatic numerals where the key is the numeral as int
4 # and the value is its 180-degree rotated equivalent (also as an int).
5 # Any numeral that doesn't have a strobogrammatic equivalent is mapped to -1.
6 rotated_numerals = [0, 1, -1, -1, -1, -1, 9, -1, 8, 6]
7
8 left, right = 0, len(num) - 1 # Pointers to traverse from both ends of the string.
9
10 # Loop to check the strobogrammatic property of the number.
11 while left <= right:
12 # Convert the left and right pointed numerals in the string to integers.
13 left_numeral, right_numeral = int(num[left]), int(num[right])
14
15 # If the rotated numeral of left doesn't match the right numeral,
16 # or if the numeral at the current position doesn't have a valid rotation,
17 # then the number is not strobogrammatic.
18 if rotated_numerals[left_numeral] != right_numeral:
19 return False
20
21 # Move the pointers closer to the center.
22 left += 1
23 right -= 1
24
25 # The entire number has been checked and is strobogrammatic.
26 return True
27
1class Solution {
2
3 /**
4 * Checks if a number is strobogrammatic.
5 * A number is strobogrammatic if it looks the same when rotated 180 degrees.
6 *
7 * @param num the string representing the number to check
8 * @return true if the number is strobogrammatic, false otherwise
9 */
10 public boolean isStrobogrammatic(String num) {
11 // An array to represent the 180-degree rotation mapping. For digits that don't
12 // have a valid rotation (2,3,4,5,7), we set the value to -1.
13 int[] digitMapping = new int[] {0, 1, -1, -1, -1, -1, 9, -1, 8, 6};
14
15 // Two pointers approach - starting from the first and last digit of the string.
16 for (int left = 0, right = num.length() - 1; left <= right; ++left, --right) {
17 // Convert the characters at the pointers to their corresponding integer values.
18 int digitLeft = num.charAt(left) - '0';
19 int digitRight = num.charAt(right) - '0';
20
21 // Check if the rotation of digitLeft is equal to digitRight. If not, return false.
22 if (digitMapping[digitLeft] != digitRight) {
23 return false;
24 }
25 }
26 // If all pair of digits satisfy the strobogrammatic condition, return true.
27 return true;
28 }
29}
30
1class Solution {
2public:
3 // Function checks if a given number is strobogrammatic
4 bool isStrobogrammatic(string num) {
5 // Define a map from digit to its strobogrammatic counterpart
6 vector<int> digit_map = {0, 1, -1, -1, -1, -1, 9, -1, 8, 6};
7
8 // Initialize two pointers, one starting from the beginning (left) and the other from the end (right) of the string
9 int left = 0, right = num.size() - 1;
10
11 // Loop through the string with both pointers moving towards the center
12 while (left <= right) {
13 // Convert characters to their corresponding integer values
14 int left_digit = num[left] - '0';
15 int right_digit = num[right] - '0';
16
17 // Check if the current digit has a valid strobogrammatic counterpart
18 // and whether it matches the counterpart of its mirror position
19 if (digit_map[left_digit] != right_digit) {
20 // If not, then the number isn't strobogrammatic
21 return false;
22 }
23
24 // Move the pointers towards the center
25 ++left;
26 --right;
27 }
28
29 // All checks passed, the number is strobogrammatic
30 return true;
31 }
32};
33
1// Function checks if a given number is strobogrammatic
2function isStrobogrammatic(num: string): boolean {
3 // Define an array from digit to its strobogrammatic counterpart
4 const digitMap: number[] = [0, 1, -1, -1, -1, -1, 9, -1, 8, 6];
5
6 // Initialize two pointers, one starting from the beginning (left) and the other
7 // from the end (right) of the string
8 let left: number = 0;
9 let right: number = num.length - 1;
10
11 // Loop through the string with both pointers moving towards the center
12 while (left <= right) {
13 // Convert characters to their corresponding integer values
14 const leftDigit: number = parseInt(num[left], 10);
15 const rightDigit: number = parseInt(num[right], 10);
16
17 // Check if the current digit has a strobogrammatic counterpart
18 // and whether it matches the counterpart of its mirror position
19 if (digitMap[leftDigit] !== rightDigit) {
20 // If not, the number isn't strobogrammatic
21 return false;
22 }
23
24 // Move the pointers towards the center
25 left++;
26 right--;
27 }
28
29 // All checks passed, the number is strobogrammatic
30 return true;
31}
32
Time and Space Complexity
Time Complexity
The given Python function isStrobogrammatic
checks if a number is strobogrammatic, which means the number looks the same when rotated 180 degrees.
To analyze the time complexity, we consider the number of times the while loop runs with respect to the length of the string num
. The loop runs until the pointers i
(starting from the beginning) and j
(starting from the end) meet or cross each other. For a string of length n
, this loop will run approximately n/2
times, since each iteration checks two digits (one at the beginning, one at the end).
Therefore, the time complexity of the code is O(n/2)
, which simplifies to O(n)
, where n
is the length of the input string num
.
Space Complexity
The space complexity involves analyzing the additional space used by the algorithm, excluding the input itself. In this function, the space used includes:
- A list
d
of length 10, containing the strobogrammatic equivalents. - Two integer variables
i
andj
. - Two temporary integer variables
a
andb
in the loop.
The space taken by the list d
is constant, regardless of the length of the input string. Therefore, it doesn't scale with n
. Similarly, the variables i
, j
, a
, and b
are a fixed number of additional space used, regardless of the size of the input.
Thus, the space complexity of the function is O(1)
, which denotes constant space complexity.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?
Recommended Readings
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.