Daily Leetcode #2217: Apr 26, 2026 - 1559. Detect Cycles in 2D Grid

本站添加: 2026-04-29

[00:00:00]Mhm.

[00:00:01]At 6:30 p.m.

[00:00:04]Uh Yeah, I'm heading toward the back direction.

[00:00:11]The rain seems to have stopped for now though.

[00:00:13]The uh projection is that it's going to get heavy again at 7:00. Oh, look at that yellow light behind me. Wow.

[00:00:22]Um let me show you this uh town part. This is like the fancy part of town.

[00:00:27]Um a lot of buildings.

[00:00:31]I don't know. I don't think that doesn't look like it's constructing though.

[00:00:34]Maybe it is. I don't know.

[00:00:36]But yeah, uh this is the fancy part of town or one part fancy part of town.

[00:00:42]And uh it we're on our way back.

[00:00:45]Hey, hey everybody. This is Larry. This is day 26 of the LeetCode daily challenge. Hit the like button, hit the subscribe button, join me on Discord.

[00:00:53]Let me know what you think about this one.

[00:00:55]Uh I'm going to do things a little bit I mean, I did things a little bit different this time. Uh I show you the intro. It's not a very descriptive intro, obviously.

[00:01:04]Can you guess where I am now?

[00:01:07]I'll be revealing tomorrow. Leave a Leave a comment. I mean, someone will probably get it before then anyway, but you know. Uh yeah. Uh let's take a look at today's problem. We have 1559 detect cycles in a 2D grid. Oh yeah, I have my like I I don't know. I'm I'm going to sleep right after this, so that's why I'm, you know, already ready.

[00:01:25]But yeah, we have 1559 detect cycles in a 2D grid. Okay, you have a 2D grid.

[00:01:32]Uh if I find any cycle, same way. What what's a cycle?

[00:01:36]Length of four that Okay, I mean, that's fine, but what does that mean?

[00:01:40]You cannot move this out that you see So okay, so basically anything that isn't just like going back and forth has to be like uh you know, a thing, right? So the smallest one is going to be um you know, just uh two two by two, right? Okay.

[00:01:57]And this one is way more intense.

[00:02:00]Um I'm trying to think whether there's anything really that complicated about this, right? Um I mean, obviously you should be able to do this in linear time, right? Uh I think if we do a depth-first search, that's already good enough, right?

[00:02:19]Um because you don't need to connect to the first thing, just need to connect to anything that you've seen so far that isn't exactly the one that you looked at, right?

[00:02:34]Uh but you could get into No, I mean, if it's depth-first search, it works. If you do a breadth-first search, it won't because if you do a depth-first If you do a a depth-first search, and then you go do do do do, then maybe you have some weird things, but um you always do a depth-first search and then just go all the way in, then I think you should be okay.

[00:02:56]Maybe.

[00:02:59]Yeah, because it mhm I want to say yes because it there's like a transitive property, right? Where if you have a cycle, >> [clears throat] >> that means that there are at least two out degrees, right? So if there's at least two out degrees for each uh uh uh well, not out degrees, just two degrees in general for each um node that is in the cycle. And therefore, and if if your depth-first search finishes for a certain branch, that means that you don't have a and you did not detect a cycle, then you did not um then that means that at some point you just don't have a two uh you either don't have a cycle or you don't have a degree of more than two, which means that you couldn't connect to it later anyway. I don't know if that made sense, but that's kind of the general idea. I mean, this is pretty pretty okay, but it is kind of easy to be uh like like I think I I do like this problem because it does really test your understanding of depth-first search uh and maybe just search in general um and allow you to kind of like, you know, I don't know. I mean, of course you could just yolo, but still. Um yeah, so >> [clears throat] >> Yeah, I don't know why I wrote it. So maybe it's done do do do All right, and then now we do something like uh something like this, right?

[00:04:44]Um if not done xy, then we um start as xy, right?

[00:04:54]Is that good enough? What else do I need?

[00:05:03]I'm also trying to think maybe force is not quite the uh thing, right? Because we could just number them, I think, right?

[00:05:12]There is some There is some like numbering thing where um if you obviously, you don't go back to the previous one.

[00:05:25]As long as you don't go back to the previous direction. If you see go Yeah, I think that's it. You don't really need a numbering system. I was thinking of a numbering system like, you know, some similar to something like a Cartesian tree or something like that or that like ordering thing.

[00:05:43]Um but um but we don't have to. As long as you don't go from the previous direction. So if it's not done, then maybe the previous direction is negative one.

[00:05:56]Um also, we should set up directions, right?

[00:06:00]Let me write it here instead.

[00:06:08]Uh I don't know why I'm writing it weird today.

[00:06:10]Uh do do do do it doesn't really matter.

[00:06:13]The order doesn't matter, I think.

[00:06:20]All right.

[00:06:23]And then yeah, um So I just write uh write Uh maybe this is just uh if I mean, I Yeah, let us let's just do do this, right? Then return true, then return false. And then that's just going to be the starter, right? The kicker, if you will, right? So then you have like sxsy, right? So then now we we could set it up. The character is equal to grid of sxsy, right?

[00:06:58]Um we set uh maybe we set to the done. Uh and then what else? And then yeah, and then we go DFS of sxsy, negative one direction, and c, right?

[00:07:12]Um yeah.

[00:07:16]Mhm.

[00:07:20]So the current xy, the the previous direction, right? And then c is just the character. That's fine, right?

[00:07:27]Um I'm trying to think how I would return the state here. Maybe I could do something like if do do do do, then return true, maybe.

[00:07:37]Or maybe in that case, then we just return this, right?

[00:07:41]So that's just like a very uh helpful starter.

[00:07:46]A very helpful code.

[00:07:48]Uh anyway, uh but yeah, um okay. So then now we go Yeah, done of s do do do, right? Um and then now we dxty and directions. This is just normal uh things. We actually want to enumerate it, right?

[00:08:09]And the reason why we want to enumerate it, I don't know why I say it like that, is that so we could do indexes not equal to p dot then uh previous direction, then if it's not equal to n uh do do do do, then we'll we'll take a look, right?

[00:08:24]Well, if it is done, uh well, we have to set up a new x new y first.

[00:08:32]If it is done, then we just return true, right? Because that means that we've seen it before and it is not the previous direction.

[00:08:40]Otherwise, um we might have to do Actually, I I was wrong about ordering that that mattering. We have to be a little bit careful only because um the index is not going to be your previous direction, right? Because you're going the opposite way. But that's fine.

[00:08:56]Um right? So if it's done, then we return true. Otherwise, if it is not done, then let's let's uh let's search, right?

[00:09:10]Uh do do do do do do do Like I said, then it's going to be two The way that I wrote this convention and then do this has a two offset. So we can just do um index plus two mod four or something, right?

[00:09:24]Uh and this is why some you know, some some of these prop properties you just kind of get uh you write it a certain way all the time and see. I I forgot to write that uh uh c is equal to grid of uh Oh, I guess it has to be here, right?

[00:09:43]Uh I I'm I'm I'm I'm missing a lot of things, honestly. If uh we have to make sure that it's in bounds. I don't know why I I I I mean, like I feel like I've never done this before or something, right? Uh but yeah, it do do do do do do. And c is equal to grid of NX and Y. That's why I didn't do um I don't know. That's why I didn't write this part cuz I cuz usually I just write them all together and today it just feels a little off as a result. Right, so we return true, otherwise we just return false. And yeah, hopefully this is good.

[00:10:18]It looks good.

[00:10:20]Did I I mean, this looks good. I just worry about time out because I forgot something. Like, if I done it correctly, this should be good. I just I'm double checking.

[00:10:31]All right, whatever. You always submit.

[00:10:35]Oh, no.

[00:10:38]I knew it. I was just kind of lazy to check it.

[00:10:41]What? Okay, so I put wrong, but I mean, it could be a logical error though. So, let's take a look at what the this is. We have C A D A A A A A D. So, there definitely is one here.

[00:10:55]But, I guess there is some like order of operation thing where I messed up. Where is it T L C I I don't even have to T L D R but I messed that up. Yeah, cuz I could start it up. I thought that I proved that I didn't that's not possible, but clearly it's wrong. I'm cuz we do we start this one, we do this one, and then maybe we go to the right. And we go back here.

[00:11:20]Now, we go down.

[00:11:24]Do do Do do do, but then here we should go here, right? Like, we see a a thing.

[00:11:32]That was the point. I don't know. I'm confused.

[00:11:35]Do do do do do do I mean, I guess we just have to look.

[00:11:46]I mean, it it could be that we just really messed up something as well.

[00:11:51]Okay, so the C we don't care. A as we said 0 1, right?

[00:11:55]And then goes 1 1.

[00:11:58]2 1.

[00:12:00]So, it goes down.

[00:12:03]Oh, why did I remove that? Hmm.

[00:12:06]The drawing.

[00:12:08]Eh.

[00:12:10]Also, what what happened? Okay, fine.

[00:12:12]Whatever.

[00:12:13]So, it goes down. Down.

[00:12:18]2 0 is 1.

[00:12:21]Down. Down. Okay, no Gucci. And then goes 1 0 0.

[00:12:30]And then 1 2. I mean, I guess I guess my my My only guess is like I I messed up on the previous direction or something. Cuz the cuz at here 1 0, it should see the 1 1 cell is done.

[00:12:49]And then um Yeah, 1 1 the previous direction is 0.

[00:12:57]0 is Yeah, I mean, it went from 2 0, right?

[00:13:04]So, then 2 2 Did I mess up the rows column? No, it shouldn't be. It's a square, right? Oh, not a square, rectangular, right? Do do do do do. If done NXN Y is equal to true, but why? Why is it not done?

[00:13:21]Huh.

[00:13:23]Weird.

[00:13:25]Okay, print NXN Y. It should go there, right? Or it's out of doubt this just triggers for some silly reason that I messed up on.

[00:13:36]Oh, I didn't I removed the other one.

[00:13:38]Okay, fine.

[00:13:42]This is kind of sad. Hmm. This shouldn't be that bad, but okay.

[00:13:48]Eh, okay. So, 1 0 do do do do. 1 0 goes to 1 1.

[00:13:56]Right?

[00:14:00]Do we not set it?

[00:14:06]Oh, I'm dumb. Cuz I I just forgot to return this. Or like I didn't check for it. So, if Wow, that's just bad coding, really.

[00:14:15]How did I Well, I usually don't do it this way, to be honest.

[00:14:19]I think the way that I usually would have done it is to I don't know how to pass anything, really. But, the way that I usually would have done this is by using a global.

[00:14:26]And I kind of wrote today I just wrote things a little differently and and this is why kind of I mean, I I wouldn't say like I I I think people over traumatize like using a pattern. And my idea is not to use a pattern, but it is to write the same consistent way so that there are no surprises. And and sometimes you just unfamiliar certain different ways or just not even unfamiliar, it's just like you know, you especially if you're like me at my skill level or at least my practice level, maybe not skill level.

[00:14:55]I just you know, have muscle memory about certain things and I usually do things a certain way. And when I do things differently, sometimes I'm just on autopilot, right? Meaning not not necessarily in a bad way, but I just don't think about it again or like I I don't re-evaluate all the things that I assumed to be true or previously true, right?

[00:15:14]So, yeah. So, something like that, I just didn't even think about it, to be honest. I you know, you saw me at when I print statements.

[00:15:22]Let's get this one in submit again. But, to even you know, see it cuz you know But, it happens. So, yeah. Otherwise, you know, our code was good. I mean, maybe it's not super fast, maybe it's not whatever, but you know, it's and when we take out the print statement, it's twice as fast. So, yeah.

[00:15:40]Like I said, this is going to be linear time, right?

[00:15:44]Linear time, linear space. This is linear space. And linear time is just we look at each cell at most once or well, at most all of one, right? Like, we could do four times up, down, left, right, or whatever.

[00:15:56]Um And yeah, and that's it. That's all I have with this one. Let me know what you think. Thanks for watching. The idea behind this cycle I I don't Maybe I should have drawn drawn drawn this out a little bit, but I don't know. Maybe my excuse is that I'm not I don't know if I was that confident about it. I mean, I had a feeling it was right, but um you know But, the idea here is that instead of like you know, looking for precise cycles, we we just kind of like we go from anywhere, it doesn't matter. As soon as we we see the same point, you know that this is the cycle. It's almost like um What's it called? The tortoise and the rabbit algorithm, right? I'm going you know, that that's the idea of that you start at anywhere and if there's a cycle, you eventually you're going to a cycle, right? And that's basically the idea with the depth-first search.

[00:16:48]Because here, maybe you know, if it goes do do do do do do and it doesn't really find anything, then now here it it backtracks. It goes here and then finds it, then that's good enough as well, right? There are a lot of ideas like that and that's what I mean by it really tests your understanding of maybe search, maybe breadth-first search, maybe depth-first search and stuff like that. So, yeah.

[00:17:11]Um Well, otherwise, that's it. That's all I have with this one. Let me know what you think. Thanks for watching. Stay good.

[00:17:19]Stay healthy. Take care of mental health. I'll see you all later and take care. Bye-bye.