Strobogrammatic Number - LeetCode 246 Explained

Ajouté : 2026-05-27

[00:00:00]Hey programmers, Alvin here. Right now, let's go over leak code number 246, the strobmatic number problem. So, in this problem, we're going to be given a number as input. What we want to do is figure out whether or not it's strobatic. And what that means is the number should look the same when it's flipped 180°. So, for example, given 6889, if I actually copy it over here, and I spin that 180°, it actually ends up looking the same. So, I should return true here. Let's go over another example. Let's say my input was 962. If I actually flip that 180°, it looks really different. So, I should return false in this instance. It is not straggy for this one. The first thing we'll want to do is figure out what digits or what characters actually look like other numbers upside down. So, here's all 10 digits. Now, let's spin it 180°. We can compare each. So, there are a few characters that are really obvious here.

[00:00:58]For example, 8 matches up with eight.

[00:01:00]Also, zero matches up with zero. And in the problem, they also tell us that one should match up with a one. 6 turns into a 9 when you spin 180°, and 9 turns into a six when it's 180°. What you'll notice is many of these characters when you flip them 180°, they actually end up looking like themselves. That would be the case for 0, 1, and also eight.

[00:01:21]However, a very important circumstance is when I have a six. When I spin the six 180°, it turns into another character, right? It turns into the nine. And kind of the inverse is also true. A nine turns into a six. And so to actually store this information, it'd be really nice if you have like a key value pairing where you can look at a character and figure out its flipped version. That would look like this. So like we see, I have all of my characters matched up. And we were sure to encode information like 9 maps to a six. When you spin 180°, we should store this information in a hashmap because we get constant time lookup. We also have very natural key value pairs here. I'm going to call this my inverse hashmap. All right, now let's go over an example.

[00:02:05]Let's say we had this input string. Uh, in the long run, we should end up returning true because this is indeed a string that looks the same if you actually spin it 180° like so, right? It still reads 68189 either way, right? But how can we come up with the logic for this? Well, the key is what you want to do is iterate through your string and look at corresponding characters. In other words, when I'm looking at the first character, I want to compare that to the very last character. Recall these are front and back pointers. And as we iterate, we want to look at corresponding characters. So, I compare the first to the last. Then, I compare the second to the second to last, and then the third to the third to last, and so on till I'm done iterating through my entire string. Now, let's go over the specific logic here. So, when I'm on this first iteration, I'm comparing the first character to the very last character. What I want to do is look up my starting character inside of this hashmap. And I can find it right here.

[00:03:01]Right, the key is six. And it tells me that the corresponding value is nine.

[00:03:05]So, that means I should find a nine on the other end of the string. Because I have a six in the front, that means I need a nine in the back. That would actually be true right now because I do have those two characters. So, I'm good to go. I need to go to the next iteration. So I move my pointers. Now I look at the second and the second to last. And again what I do is I look up my front character inside of my hashmap.

[00:03:26]And there I find it. Its corresponding value is an eight. So that means I have an eight in the front and I need an eight in the back. And I do. So I've actually verified these two characters as well. Finally, on this last iteration, you'll notice that both of my front and back pointers, they actually point to the same character. That's okay. I can still run the same logic because one should map to a one as well and those match up. My front character does match my back character. At this point, I'm done iterating through my entire string. So, I can just return true. Do note that when your string has an odd number of characters on the very last iteration, your front pointer and your back pointer are going to point at the same character. But you still need to verify if it exists inside of the hashmap. For example, think of a string like this, right? We know that when we actually spin this 180°, this does not match up, right? The four in the middle doesn't look like anything. So, it should be invalid.

[00:04:19]So, just bear that in mind. Let's go over another example like this one. So, here we have 69189.

[00:04:26]When we actually spin this 180°, it does not look like the same number. The number starts 691, but when you flip it 180°, it actually reads 681. So, that's why we return false here. Let's go over the logic. We're going to start in the same way. So we have our front pointer and our back pointer. And we look up our front character in our hashmap, which I find right here. Tells me that the corresponding back character should be nine, which is exactly the case right now. So I verify these two characters as correct. And so I go on to the next iteration. Here's where things get interesting. When I look up my front character in the hashmap, I can go ahead and find the nine. But I notice that things don't match up here, right? My front character is a nine. uh and my rear character should be a six, but I actually have an eight inside of my string. That's where things go wrong.

[00:05:12]So, at this point, I found a mismatch. I can just automatically return false.

[00:05:16]It's not the case that this number is strobmatic, right? It doesn't look the same when it's span 180°. All right, that's really all there is to this algorithm. Let's go ahead and summarize the complexity here. If we say that n is the length of our string, the time complexity here is just going to be O of N. Coming from the fact that we just iterate through the entire string. Let's say we had a very long string of ones like this. You can imagine I have my front pointer at the beginning and my back pointer at the very end. We just, you know, bring these closer to each other one step at a time. On a single iteration, we move the front pointer to the right and we also move the back pointer to the left. So really, the number of iterations you need is n /2 because you really take two steps at a time. But because we're using big O notation for this, you can simplify N /2 to just N. That's why the time complexity is just O of N. The space complexity here is just constant.

[00:06:08]Although we use a hashmap to store our inverse information, that's going to have a fixed size. Right? Notice that the literal a hashmap you're going to create, it's only going to have five different entries. So we say that it's constant space.

[00:06:21]All right. So let's go over the code for this one. I'm going to start by creating that hashmap that I could refer to all of the characters as well as their appropriate pairs. So, I'll call it my inverse char. Make it a Python dictionary or hashmap in whatever language you're using. I'm going to have one matches up with a one. I also need zero matches up with zero. And there are a few other pairs here, right? What I'm going to do is also have six should correspond with nine.

[00:06:50]And also eight matches up with eight.

[00:06:54]Finally, I need nine and six here, right? So nine matches up with six.

[00:07:00]Great. And so I know that if a uh input string is going to be strawberic, then it needs to have only these types of characters, right? So I'm going to start iterating through my num. And do bear in mind that num is actually a string type here. So careful there. And I'm going to actually grab just the index. So I'll say for i in range from zero up to length of num. And like we said in the whiteboard, what we want to do is grab corresponding characters at the front as well as the back. Right? So I'm going to grab front. Your front is just going to be I or rather the num I. So grab that character and your back is going to be the corresponding character at the end.

[00:07:38]Right? So I'm going to show you how to write this manually. Then of course I'll show you the nice Python way of writing this. So if you're writing this in like another language, you have to be a little careful with your index arithmetic here. So I'm just going to have a little example here. I'll say it's 6 88 9. And below it, I'm just going to label the indices. So they go 0 1 2 3. Great. So we know that in the first iteration, I is going to be index zero. So it's going to be element six, right? And we want to do is have that correspond to the very last element, right? We know that in general to get the last element of a string or the last index of a string, you could do length minus one. So in general if you do the length of num minus one it would always be the case that this expression refers to the last character in your string right if you want to have this always match up with the appropriate character then you want to additionally subtract i right so on the first iteration uh i is going to be equal to zero so you grab this character and then in this you're going to do four minus one right which is three minus 0 which is still three right and So you would grab the six and the nine, which is good to go. Right? On the next iteration, I is going to be one. So you're going to grab this eight and you want to match it up with this eight over here. So we'll check our math. We do four minus one, which is three minus another one is going to give us two, right? And that would give us the correct correspondence. So this is a general pattern you can use to attract characters at the front and back at the same time. But if you're in Python, you could just simply write this asgative -1 minus i. Great. Because in general, negative 1 is always going to refer to the last character of your string. And then from here, what I want to do is now check things. So I'm going to check if I have a mismatch. I'll check if front is not equal to inverse char of back.

[00:09:33]Great. And if that's the case, I want to return false. And the place you want to return true is only after you're done verifying everything. So you write a late return true here.

[00:09:44]Great. Let's just go over maybe this small example just to make sure we're trending in the right direction. Right?

[00:09:51]So we know in the first iteration we have our six as our front and the nine as the back. And here I'm checking if the front, in other words, if the six is not equal to the inverse character of the back. Well, just bear in mind back would be just the nine. So when I grab the inverse character of the back, right? I'm keying in with nine. I'm getting the six, right? So this is checking if six is not equal to six, right? Which is false. So I don't return false here. That's why ultimately I actually verify this is true, which is good to go. Great. There is something missing from this code, but we could fix it together. It's pretty common mistake, so I want to kind of debug it. So you'll notice that I'm failing on an input where I have 962, right? And really, I'll just kind of cut to the chase here.

[00:10:34]Notice that I have a two in my input string, right? And so if you actually look at our code here, two is a character that doesn't actually have an appropriate inverse pair. If your string contains a two in it, then it can't possibly be strobmatic. If a character just isn't present within that inverse char, then I just want to return false as well. So I'll extend this. when I check if back the back character is not in inverse char then it means I have something like a two or a five something that just doesn't even have a pair so I want to automatically return false. So I'll go ahead and give this a run now.

[00:11:08]And there we have it. I hope you found this video helpful. If you enjoy my teaching style then I think you'll love my full data structures and algorithms course at structy.net. Atructy.net net.

[00:11:20]I've designed a beginner-friendly DSA course that is way more effective than just grinding le code. The truth is, like you've probably felt, le code is not a great platform for learning algorithms because there's a steep learning curve and the explanations are all over the place. But in my course, I've designed each problem so that it builds on top of the last. So, you'll really feel the progression. The best part is I'll be there to explain each problem using the same clear animations and code walkthroughs that you saw in this video. So, if you want to prep for your interviews without the frustrating leak code grind, then head to strructy.net. You can start for free today. I'll leave a link in the video description if you're interested. I'll see you there.