Storing state in O(1) space? | Leetcode With Vim

All right. So, we've got a pretty interesting question today. So, this [music] is Conway's game of life. So, you guys have probably seen Conway's game of life before. If you haven't um well, it looks like this. And what it is is actually given in the description here. So the board is made up of a grid of cells where each cell is either alive or dead. And each time that the game updates, they will have these interactions. So any alive cell with two um with fewer than two neighbors dies. Any cell with two or three neighbors lives. Any cell with more than three neighbors dies. and any dead cell with exactly three neighbors becomes alive. Um, and what we want to do is that given a board, right, we would like to apply all of these rules. Now, to solve this in place, right, cuz um, one obvious way you could do this is by creating a whole new board, right? using the old board as a reference of the previous state, creating new board with the new state uh and then just replacing the whole previous board with the new board. However, if we want to use constant memory, we want to be able [music] to solve this in place. Now, since we're given a vector of integers, right, not a uh a vector of booleans, uh it kind of hints as to how we might solve this. So uh to me the easiest way to solve this is just by using two other states such as two equals going to be live and three as going to be uh dead. Right? So we can we can sort of have the actually we should probably swap swap these around. So zero is dead, one is alive and two is going to be dead, three is going to be alive. Right? So by modifying the board in place, we can store both the original which is like like was alive going to be dead was dead going to be alive. [music] By having all of these states, right, um, we can store both the past state and the next state at the same time. So, actually, um, I think it's best if we do it like in this. Yeah. Okay. Um, so let's try it out. So obviously we want to uh go through every single board. So for I mean obviously we want to go through every single cell. So um let's create two variables. Uh n I can't forget I keep on forgetting which one is m which one is n. [snorts] I guess for these this purpose it doesn't really matter. We'll just say something board zero size. Okay, cuz the first time we're going to be iterating through each board and then the second time we're going to be iterating through um actually wait the first time we're going to be iterating through each row and then the second time for each row we're going to be iterating through each cell. So this would make sense. All right. Um, so one way that we can do it is put a bunch of complicated complicated logic in here. Um, or we can try to move the logic for determining the all the rules uh of the game of life into uh some helper functions. So let's go ahead and do that. So let's have a um a function that returns a boolean obviously and let's call it sur right survives and it takes in a board just so we know um obviously we need the board and then in I and J which represent and let's just say the y and x axis not y and x coordinate okay represents a point [music] uh or a cell within this board um so let's do the current state is going [music] to be uh board yx this is the current state of it and If the current state is one or alive. Yeah, if this is alive or it can be dead. Now remember, since we're only going to be applying this survives on new uh new cells, we don't have to check for two or three. So honestly we can just do if [snorts] uh we just do if cur. Sure that makes sense. Um and if it is alive we want to apply um these rules. So we want to get another helper function right that get that returns the number since all since all of the rules um all the rules depend on how many neighbors it has [music] right we all we want to do is figure out how many neighbors it has and then there's just going to be a few if statements so we should create a another helper function that just returns neighbors return its neighbors. So that's given the board and the coordinates to the cell. Um let's figure out how many it has. Uh so we can pretend that's pretend this works for now, right? Pretend this works. Write that down. Imagine we have the number of neighbors equals neighbors of the board y and x right. So if and then then we can apply the rules according to this. So if n is less than two, right? So if our cell is less than two neighbors, [music] we're going to return false, right? we return uh false because our our uh what's it called? We're not going to survive. And actually instead of survives, we can just call it next state the int. [music] And now we can use our uh our integer states of zero up to three. Um so if n is less than two we say that it was alive but going to be dead so we return three and else if n is equal to three I think exactly three right two or three so n is equal to two or three it's going to we're going to stay alive. Uh so we're going to return one which is alive and still going to be alive. Um or else we return three. So actually to simplify this instead of checking all these like one rule at a time uh we can see that these two return the same thing. So we can actually just have one if statement. If n is equal to two or three it's going to stay alive otherwise return. Okay. And if the cell was originally dead, any dead cell with exactly three live neighbors become uh becomes a live cell as a value reproduction. So we say if n is equal to exactly three we can return four which is not four two which is was dead but going to be but going to be alive. else going just return uh which is here. Okay. And there's probably other ways to [music] simplify this but we'll just leave it like this for now. Now for each um now if we iterate through all we have to do is just say board i j is equal to next state of the board pass in the board we pass in the i and j as x and y um and then that's all we have to do right we have a very very simple uh main function right or not a main function but this is the the function fun that we call and then we put all the like logic in helper functions to help separate right we have next state and next state requires neighbors to work um so let's implement this right now so how many neighbors does it have well we we run into a sort of interesting um issue where if we just get like the board y - one x right x - one um and then we do this for you know however many ones uh y - one or x - one could be less than zero just like they can be greater than the length of the uh array or the dimensions of the matrix. So, one way you could handle this, let me just think um [snorts] could create another helper. Um, but I think it's fine. First of all, let's let's uh uh let me think do a few if statements. I'm going to do a bit of a a few for loops um just to make this code a bit. So I is to one and we can call this i J. [snorts] So now this is going to loop nine times if u i = z and um we have int n which is going to keep track of the number of neighbors and we're going to return the end here. Now if um we'll just write this assuming that um we will never go out of bounds. So I pl so we have y + i and x + j which is going to go through all of the board's neighbors. Okay. And I'm going to say if this is equal to uh let me see one or three. So one or uh this is equal three. We're going to increment n. And then to be a bit cleaner, we'll just say C for cell is equal to this. So uh that now we have to make sure that C stays within the bounds of the matrix. And to do that we can write a we can write more if statements or we can extend this uh this guard at the top to make sure um both that we don't include the cell itself as its own element and also if y + I is greater is less than zero or I + I is greater than the board size. This is where it gets a bit messy. Um I + J is less than zero or X + J is greater than board zero. That sucks. And let me make sure that the board will always Yeah, board will always have at least one element. I mean, yeah, the dimension is at least one. We're not going to get a board with nothing on it. Then, yeah, that should protect against going out of bounds. And if we try to submit our code, we'll hope we'll hope that it works. Let me just make sure by you know running through the program again. Um we have m equals for size and equals this size. We iterate through. We set each of these to next day. All right. It doesn't work yet. Almost forgot. Um actually let's just see. Right. If we run it, it's not going to work. But hopefully there will be no errors. There is an error. Why is there an error? I mean, I'm assuming this means that we tried to access a um an array index that was out of bounds. What happened something here? Somewhere here. I'm pretty but the and already evaluates first or uh let's see or is less than zero or plus I is greater than oh see it's greater or equal to boards uh board size let's just try to do that in and we we obviously won't get the correct answer because of this, right? We have the uh the threes and twos which weren't a part of our of what we wanted to return. We only wanted to return one and zero, you know, alive or dead. But you can see every single uh three corresponds to an expected zero. Every single two corresponds to except uh to an expected one. So three 0 2 1 same thing here two one. So pretty much we have um stored this information of the previous and the next state. Now we just need to turn it to back to zero and one right. Um and to do that we just say if board I J is equal to two right we set it equal to one because it it it's going to be alive again and if um it's equal to three we'll set it equal to zero and I forgot what I copied I think I just copied this for loop seconds, right? And then if we run it now, uh we should expect that we get the correct answer. And if we submit to uh check all the other test cases, you'll see that uh the code works. So yeah, um yeah, overall it's it's an interesting question, you know. Uh there are definitely some better uh ways you can write some of these functions. Like for example, instead of just having like a comment that explains uh what each of these integers mean, uh this is like a prime example of why you would use an enum, right? So for example, you have an enum uh uh what should we call it? enam state and the first state is dead. Uh dead and dead then dead. We have alive then alive. I don't know if this is the proper Okay, whatever. Uh and then we have dead then alive and alive, right? So replacing all of these like they call them like magic numbers, right? We don't we have no idea what two and three or one or zero means unless we look at you know this comment. Um but being able to have an enum like this, we can sort of replace these like if um if the actually this is the number of neighbors. Yeah, that's fine. Um, then here we didn't return alive then alive. Alive then dead, right? Dead then alive or dead then dead, right? So like this [music] makes a bit more sense just like um how here we can check if the board was equal to dead then alive right we return alive and if it was alive then dead now it's just going to be dead anyways I started yapping Uh yeah there there's not much left to be said you know there's all sorts of ways you can write the program uh and at the end of the day the important thing is that uh you recognize a solution you're able to you know break them down either write them in a nice way right in a in a you know very neat concise way or if you can't do that or you don't have the time to figure out how to write it in a concise way. You know, just break it down to helper functions, right? So each individual function is easy to read and comprehend, right? So for example this game of life function it's very easy to read this and be like hey all we do is you know what we can do is set each board uh cell equal to the next state that it should be in given the you know whatever this function returns. And then after that we can set all all of the states from you know if it's dead then alive uh set it to the actual alive state right if it's alive then dead set it to the actual dead state and then you know next state you just be like hey we get the number of neighbors we apply uh the rules to alive and dead cells and of course count neighbors um looks terrible, but you can sort of tell uh this is just to stop it from going out of bounds. And if uh we have a neighbor that is alive, which is let me count let me uh alive then alive or before was alive then because we're using obviously the previous state. Um, yeah, we count that as an alive neighbor. So, yeah, that's pretty much the video. Hope you guys enjoyed. Let me just resubmit this new code. Um, I don't know if you can I don't think you can define an enum within the class. that make much sense. But uh we'll do this. Accepted. Yeah. So yeah, that's going to be the video. Hope you guys enjoyed. Uh leave a like, subscribe. I'll be making uh more videos soon on more interesting topics probably. I'm getting kind of tired of doing the codes. Yeah, that's it.

Leetcode #289. Game of Life. Coding With Vim: https://www.youtube.com/playlist?list=PLmTrCsxAaghW9KWrzuc6n2B9ud2uV5sjK Github ► https://github.com/nycrat Twitter ► https://twitter.com/VimSalesman