Daily Leetcode #2218: Apr 27, 2026 - 1391. Check if There is a Valid Path in a Grid

Añadido: 2026-05-05

[00:00:00]Uh I have a feeling I would maybe be back later, but it's not super clear. Uh but originally my plan was to leave from here anyway. The reason being that the reason being well and it turned out to be the right move is that there there would be cars here. But even aside from that, there's the uh the bizarre over there uh the markets. So I could maybe go pick up some souvenirs. I'll do that now and then we'll see if I can optimistically uh you know optimistically see how to get back uh once again. Now I am here.

[00:00:41]This dude doesn't even have a real uh modern horn. Just a squeaker which I think is good enough and it gets people's attention.

[00:00:54]I don't know.

[00:01:00]And our first stop will be the museum.

[00:01:01]We still have plenty of time. So yeah.

[00:01:08]Hey. Hey everybody. This is Larry. I'm here in Sona Gan.

[00:01:13]I hope I'm saying that right. Hit the like button. Hit the subscribe button.

[00:01:16]Join me on Discord. Yeah. Let me know what you think about today. And yeah, it's just just checking out the architecture. It's very beautiful here uh in the old ancient city. Uh right now I'm in the museum portion of it. Uh and yeah, we'll check it out. I think we're basically almost back at the entrance, ready to head back. This also it's a place where a lot of bros and alike uh are taking Instagram selfies and all these things. So I guess that's what this is good for. there are a lot of beautiful architectural, you know, arches and stuff like that which lends uh very easily to that kind of uh thing.

[00:01:54]Um but for me, I took a quick selfie or two, but I you know uh yeah uh now I have to try to figure out where to call an Uber from. Um and then well actually just take the Uber.

[00:02:09]Hey everybody, this is Larry. This is day 27 probably of the leo day challenge. Hit the like button, hit the subscribe button, join me on discord.

[00:02:18]Let me know what you think about today's prom. Um yeah, as some of you guessed, I am here in Bangladesh in Daka. Uh don't obviously in the intro I went out to uh Sona Sona Gen Go apologies.

[00:02:37][laughter] So yeah, so that's basically it. That's what I'm up to. Uh, tomorrow I'm going to try to go see the old city. Maybe that's a spoiler if you want to wait for that. No, but tomorrow morning I probably because my flight is tomorrow evening. I probably have to do the video tomorrow morning. So, I probably won't have too many clips until the day afterwards or something like that. I don't know. We If you want to see old leave uh and if I'm saying it incorrectly, let me know in the comments and I I'll try my best.

[00:03:07]Uh either tomorrow, the day afterwards or one of these days, you know, I mean, I was gonna say I'm not going anywhere, but I guess I'm going everywhere. But, you know, the videos will, you know, unless they don't get backed up, then, you know, things are sad, but otherwise, it should be okay.

[00:03:22]Okay. Uh let's take a look at today's problem. Uh hope everyone's enjoying it.

[00:03:27]I'm still in the hotel with good AC.

[00:03:30]It's very nice. I have to start packing afterwards. So, yeah. Well, I mean, I didn't unpack too much hopefully.

[00:03:37]Anyway though, let's take a look. Today we have 1391. Check if there is a rout path in a grid. You have a grid each one of this street and you have six of these which are I guess these six variations.

[00:03:49]Uh we might have to kind of um might have to uh figure out how to represent this. But uh okay. So what are we trying to do here? Uh you would up start at the upper left and then you're trying to go to uh bottom right. Um and you cannot change any streets and there no like intersection. So there's no decision.

[00:04:06]You're just trying to simulate where you can go from upper left to lower right. I think um I think I've done something like this in the sense that well I mean this problem of course just to be clear but also like I think it reminds me of like those video games where you're just playing around and stuff like that. So definitely uh something that's useful.

[00:04:24]Uh there there a couple of like I mean one of them maybe just like a road game but another one is called like is it called pipe dreams or something like that where you they're pipes. you have like liquids forming from the left side and you're trying to get them to the right side or something like that. I don't know. Does that ring a bell? Let me know in the comments. Or am I making games up? Maybe it's not called pipe dreams, but something with pipes and it's not Mario. Mario also has pipes, but that's another um Yeah, that's another thing. Okay, but I mean I think this one I think everyone it should be straightforward um in understanding right in algorithm, right? Like I don't think there's anything tricky. There's nothing to like think about or learn with respect to the math part of it, the al algorithmic part of it. What we want to try to figure out is just how to represent this, how to do data structure. I mean, of course, the the the uh the simplest maybe way is just uh a lot of if statements, right? Uh and you could probably do I don't know there probably a lot of if statements depending on, you know, where it comes from, right? Um let's maybe try not to do that. I mean we can we have to. I mean sometimes end of the day you know if you want to solve the problem you have to do the annoying crap work and sometimes it is that way but um but you know with experience you can try to figure out if there are better um in this case data representation. Sometimes it's data structures um just to even make not alithmic data structures but data structures that allow you to write cleaner code. And cleaner code is in a way that is just easier to write, right?

[00:06:03]Um easier to write means sometimes it's shorter, sometimes it's not, but it also just means that it's harder to make mistakes, right? More difficult to make mistakes, easier to get right on the first go. I think these are the things that uh I would um you know, think about in general, right? Um okay, so uh the first thing I have to do is represent these six things, right?

[00:06:26]Um, how do I want to write it? I mean, uh, okay. So, maybe the the first thing is just draw out a square, right? Um, it's kind of tricky because because let's say street one connects left and right, right? But you don't always go from left to right. Sometimes if depending on where it comes from, it can go from right to left. So, how would I want to write it, right?

[00:06:49]I mean obviously each um cube or not cube but square only has four things and you have to represent um yeah you have to represent uh you know which way it goes out right how do I want to do that what does it mean to be coming from the left. So, okay, you have a cell. You're coming from the left.

[00:07:22]Um, so maybe we we just go um maybe we just go Huh. I mean, again, like we said, we can if it needs to, we can do a lot of if statements, right?

[00:07:45]I'm just trying to think like uh what is the best way though and it may be that there isn't a good way and maybe if statement is right um but I mean okay instead of overthinking it sometimes though uh you could you know you don't have to write clean code the first time you could refactor to things halfway or you know as you kind of know what you're doing right now I'm still not quite sure what I am doing and that's why the data representation is hard right once I figure out what I want to do then it should be easy so maybe we'll just pretend we have some magic things first and then we'll write out the simulation which is what this is right so then now we go okay so maybe x is equal to y is equal to zero right that's first so then uh we don't have to visit all cells or anything like that right we just have to kind of go Um yeah okay so then maybe we write have something like while true um okay if x is equal to um okay we have to write rows and columns so so maybe you write something like this right um and then if this is equal to uh minus one and y is equal to uh I my computer's uh then we just return true right because we went to the end otherwise what what are we doing right so then now maybe we have a previous direction right uh so in this case um I want to say well previous in this case oh oops misspell return uh in this case previous is technically if you're on the upper left it's either coming from the left or coming from the up, which is kind of confusing because then you could also have some like weird ones. Like if you have street >> [snorts] >> uh five, then that's a little ambiguous.

[00:09:54]But uh okay, well, we could special case that I guess.

[00:09:58]Okay, so maybe Okay, so here we I want to write something like previous is equal to something, right?

[00:10:09]Uh and then maybe we write something like uh if grid of uh 0 0 but we can write xy right oh they just give you the number huh so we actually need to kind of map that precisely but let's just say uh okay so this is the number right so if if left is in this uh maybe I could look up.

[00:10:39]If left is in this, then previous is equal to left, right? Because now you're coming from the left. Else if up is in this, then we're just coming from the up right. Previous is equal to up. Uh is that right? Yeah, maybe that's fine.

[00:10:58]Right? Because then now you you match the other one, right? And then now we have to do up, down, left, right. Um uh maybe I've done left. It's not that important, is it?

[00:11:12]Maybe it is. It's fine. So left is you go to uh Yeah, I guess is this kind of I'm just trying to think what I want to do. Okay. So let's look at let's write the grid first then right uh the uh is it 1 2 3 4 5 six. Okay. So this is silly because this should be minus one then maybe uh okay we'll just use this look up. So we use a map instead.

[00:11:51]Right. And then you have one is to go to say uh okay left right right spelled correctly for somebody. Uh two is you go to up down.

[00:12:05]Three is you go to left down.

[00:12:11]Four is you go to uh right down maybe I don't know if the order matters too much honestly but it's I don't know left up and then uh right up right. So these are the six things and of course we now have to define them. Um I think this is fine maybe left.

[00:12:39]So up down left right let's say up down up down left right is equal to I know I could well be a little bit smart about this but let's just write this bit. Um okay so then now we have the previous right. So, we set the previous uh and what does that mean? I mean, this is fine, but I also have to write something like directions, right? Um because then you don't go to the next one, maybe. I don't know.

[00:13:12]Yeah. So, up is going to be um minus one on the row, right? Uh down is the other direction.

[00:13:25]Left is oops not that right is that right? So you have this maybe. So then now previous is equal to uh let's just say you know oh actually I guess it could be just negative one. And then if neither of these is true wait what happens? Maybe I misread this actually. Um cuz it could be that like the upper left is road uh with street I guess actually if upper left is street four then that's the tricky one right cuz one two three well yeah five would just probably be wrong and six I guess six is still possible so five would just be wrong and but four what happens Four.

[00:14:22]I guess four. You could go in either direction and that's the tricky part, right? Wow. This is I actually didn't think about that case. That is really annoying.

[00:14:39]Maybe I can just do a first search or death first search. Either way, doing a search. Maybe this was a misguided um Yeah. What am I doing? This is uh I think I over complicated this a little bit. Um okay, let's say we don't need any of this for Well, probably still need lookup uh and directions because they all kind of map together. Okay. So then now we have just this, right?

[00:15:13]I don't know. Maybe the previous cuz I I cuz um honestly street four made me rethink it because my initial idea was just okay well you only have one choice to go to the next one but then street four I guess makes it so that you can go either way and that changes the complexity a little bit right so here maybe I thought maybe I didn't have I thought it was just simulation to be frank uh I didn't really think about it too much but now we can just do breath first search which is still kind of simulation e if you want to call it that I just connected components now, right?

[00:15:45]Um, yeah.

[00:15:52]And then maybe we just write something like done, right?

[00:16:10]Uh, true. Something like this. And then you know this is regular buff search now right and let's rewrite this a little bit to be more of my usual breakfast which e okay right so somewhere like this now And then now um yeah we go um okay so for let's just say d for direction in lookup of grid of xy don't know how that happened the grid of xy um so then that will give us the directions so that's for d so then now um yeah dx dy is equal directions of d, right? And then nx and y is equal to x plus dx y + dy.

[00:17:20]And then now we can do um you know our usual referral search stuff. I don't know why. I guess I complicated things way too much before because I I mean in some way it is a premature optimization but it's not even correct. So it's hard to kind of uh justify it that way. But yeah, and then now you go out, right?

[00:17:39]And then if not done, nxny, then q.appen nx nxny. And then we uh Yeah. Or set it to done. That's what I I was like, I'm missing something, but forget what it was. Uh yeah, and then that's it. If we did all the first search, then we just return false, right? And this is sloppy.

[00:17:57]And it's not even right. What's 112? So, okay. Oh.

[00:18:03]H. Well, this is I I mean I I think I Why is this for I mean I think this is force, but um but I'm wrong anyway. H I mean uh uh I mean number two number I'm just looking at number two. I know number three were wrong obviously but um but I think I interpret this wrong with BFS. That's why I didn't do it. I think now I remember I I had this idea of why I didn't do it but then I just kind of got forgot because of example. But yeah, the idea here is that well these two votes are not connected. So we have to add a little bit thing and I think this is what I was trying to avoid with a lot of if statements but maybe it's fine.

[00:18:41]It's okay. So that means that um okay so we have the D which is the direction right?

[00:18:48]Uh so we have to kind of have the opposite u and the opposite the way that I wrote this opposite is kind of weird um unlike what we had yesterday. Um, what I mean by opposite is that um, if you're going to the right, right, then the the right cell would have to have the left, right? That's basically the idea. And maybe you could even just write in a in a dumb way. I'm going to write it. I mean, you could actually write a map for this, but maybe um but maybe uh I'm just being dumb today, right? So left, let's map that to right.

[00:19:28]right map bit to left. My computer's lagging, so it just looks like I'm, you know, typing weird.

[00:19:35]Okay, I mean, this is really dumb, of course, but uh but it works. I just want to show you that sometimes, you know, whatever, right? Uh so, okay. And um so, and the opposite of D is in the new cell, right? So, grid of NXY.

[00:19:54]Um, so that is and then the lookup of that is what I mean. Yep. Right. So then that's that's how you know they're connected. So let's run it again.

[00:20:05]Hopefully this fixes it. Uh, like I said, it's silly looking, but if it works, then that's fine. Let's give a yellow submit. Not super confident. I have a lot of silly mistakes and everywhere. Okay, fine. So that looks okay. So that looks good. Um you could of course as I said um replace um this thing with a formula but like you know you like I think we yesterday we did it with a formula. I don't remember yesterday's for problem but I think we did something similar. Oh I don't remember whatever.

[00:20:33]Um but yeah but that's it. That's all I have for this one. I mean this is breakfast search right? So it um there's really not much to it once you recognize that you know easier said than done.

[00:20:45]speaking as someone who well you watched what I did so uh but still doable so yeah uh did and as a result of it being breath of search this is going to be linear time linear space nothing too nuts right uh and that's it that's what I have for this one let me know what you think for watching stay good stay healthy to your mental health I'll see y'all later and take care but before I go if you're still watching uh yeah guess where I'm going X that's it. Uh I'll give you a hint. It is not India. I would love to go to India. I mean people ask me why I don't go to India. Um and it's not actually be I mean I've been to India before. I've been to New Delhi. Uh or just Delhi uh Japur and Agua. I mean you have to do I mean I don't know right. Um and I loved it a lot. Uh I liked India a lot. Um just like I like Bangladesh a lot to be honest. Dhaka I know it's very intense and I know there's a lot of honking even now and I'm in hotel but um but you know I don't mind it. It's fine. Uh but the reason why I don't go to India and I would love to do a day trip like there was a plan this is very long. I don't know if anyone's watching this. If anyone's watching this still, let me know in the comments. But uh but I would yeah there was a uh like you know a lot a lot of my trip is way uh like I only planned out like about a week in advance. So it's not like I have the entire trip planned like so nothing is set in stone. I don't know where I'm going next week, right? Uh I know where I'm going tomorrow because that part is a little bit important. Uh but yeah. Um what was I going to say? Oh yeah. The reason why I know India um is not you know I love India. I would love to like I've said I've been to those three cities and I also been to Bangalore. Uh so I've been to those four cities. Um I would love to see more um you know Mumbai obviously uh Kolkata maybe um and you know a couple of places but the reason is because they just have very uh very strict drone laws. I mean if you watch some of my videos you know that I I fly my drone everywhere. Um, and I don't need to fire it. Just to be clear, like I didn't fire him in Badash because it's already illegal here as well. Um, or annoying to for a foreigner to get the permit or whatever needed. So, I don't fry it and it's fine, right? But the thing with India is that they confiscate your drone at the airport.

[00:23:15]Uh, and I've already I mean, even if I have a cheap airport, I probably wouldn't do it. But if I had a cheap drone, I probably wouldn't do it. But I have a very expensive drone and I'm not going to risk uh like the only way you don't get confiscated is if you sneak it in somehow. And I think like they still scan you on the way out. So they might catch you on the way out, which is just as bad if they confiscated on the way out, right? Um so yeah, that's that's the short story.

[00:23:41]Uh I I would love to go. I would, you know, but uh it's it's too expensive of a trip if they take my drone, right? So yeah. Uh so that's the hint. It's not India. Let me know your guesses. Leave a comment. Leave a like. I'll see you later. Stay good. Stay healthy. Take good mental health. I'll see you later.

[00:24:00]Take care. Bye-bye.