Theres no way anybodys doing this with O(1) space complexity in their first try in an interview setting with only 30-45 mins. Thanks for the explanation, helps a lot.
whenever i see a solution is thier for any problem on your channel it assures now i will get to understand this in best possible way..thanks for such quality videos keep going man ...
In case anyone found the mapping confusing, I found you could do this and it also works. (To me, it was a little less cognitive overhead): 0 -> 0: 0 1 -> 1: 1 0 -> 1: 2 1 -> 0: 3 0s remain 0s, 1s remain 1s. If board[r][c] and count not in [2, 3], mark 3. If board[r][c] == 0 and count == 3: mark 2 Final loop: Flip 3s to 0, 2s to 1
class Solution: def gameOfLife(self, board: List[List[int]]) -> None: """ Do not return anything, modify board in-place instead.
0 -> 0: 0 1 -> 1: 1 0 -> 1: 2 1 -> 0: 3 """ def count(r,c): cnt = 0 for i in range(r-1,r+2): for j in range(c-1,c+2): if ((i==r and j==c) or i==rows or j==cols or i
@@NeetCode just divide by 2 instead of looking for 2 or 3. Similarly you can do mod 2 to get the fist bit. In cpp i just shifted into bit 2 since it's clearer that way.
Or you could just assign each cell its value shifted by one so it will be the most significant bit (out of two): cell >>= 1; //at least in C/JS/etc, not sure about Python (Edit) oh, haven't noticed that Alex already mentioned it
Like it is shown in the video, we can go ahead with the mapping: 0: 0,0 1: 1,0 2: 0,1 3: 1,1 But one neat trick to check neighbouring initial alive cells, is we can just take whatever value we have and do '%2'. say, a visited cell would have been "1" when its updated cell value%2==1. (From above mapping, 1 and 3 would get "1" on "%2"). For an unvisited cell, the initial alive value would be 1 which also when you do "%1" you get 1. Once we populate the array with new values, just do integer "/2" on all the values and you will get correct final states.
I don't know whether that's really saving memory. You add an extra bit to every field instead of making a new array which kind of defeats the purpose of saving memory Although yes if you have integers anyway might aswell do that
Really nicely explained man but why not simply map as follows: 0|0->2 1|0->3 0|1->4 1|1->5 So while checking if cell=0 OR 2 OR 4 , it means it's a dead cell cuz 2,4 were originally 0 i.e, dead AND If cell=1 OR 3 OR 5 , it means it's a live cell cuz 3,5 were originally 1 i.e, live AND at end when we have updated each cell , if cell=2 OR 3 make it 0 cuz 2,3 are new 0s AND if cell=4,5 make it 1 cuz 4,5 are new 1s.
I had no idea you were supposed to use the original numbers, I thought you were supposed to do something insane like try to update the value, it's neighbors recursively.. which wouldn't make any sense
Cam anyone explain why when specifying the range in the count neighbours function it goes to r+2 and c+2? I thought it would only need to go +1? What am I missing here?
Because this nested loop will go through 8 directions from top left, ie. r-1, c -1 to r+1, c +1. Since python for loop doesn't count the last element, so if you want to get r + 1, you must finish range with r + 2
Hi...i have implemented Conway game of life in Python. It works very well if you draw your initial configuration "by hand" using your mouse. Now I want to implement some famous initial configuration (for example a gun or an oscillator) but I don't want to copy it using the mouse...I'm looking for a way to import the grid of a particoular configuration...do you have any idea? Thank you
save the layout of the shape using deltas (some initial middle square plus deltas in rows and cols which give us the shape). Hover the mouse around which changes the position of middle square and the deltas take care of constructing the rest of the shape. I hope I am not too vague.
I paused the video and couldn't find the solution... because I took the problem in a quite literal way and was representing the playing field as a bitmap. So, using 2 bits per cell is actually doubling the memory used.
Is it just me that found out that this solution does not solve the leetcode problem (typed all the code)? Wrong Answer Runtime: 21 ms Case 1 Input board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]] Output [[0,1,0],[2,0,3],[1,3,3],[0,2,0]]
Theres no way anybodys doing this with O(1) space complexity in their first try in an interview setting with only 30-45 mins.
Thanks for the explanation, helps a lot.
Freaks like that exist
whenever i see a solution is thier for any problem on your channel it assures now i will get to understand this in best possible way..thanks for such quality videos keep going man ...
@AAYUSH CHHABRA....whenever I see your comment on a Neetcode/Codechef video, it assures that it is a important concept ! 😀
No.1 leetcode tutorial! someone who actually can explain the problem and solution very clearly. Good job and keep up good work
In case anyone found the mapping confusing, I found you could do this and it also works. (To me, it was a little less cognitive overhead):
0 -> 0: 0
1 -> 1: 1
0 -> 1: 2
1 -> 0: 3
0s remain 0s, 1s remain 1s. If board[r][c] and count not in [2, 3], mark 3. If board[r][c] == 0 and count == 3: mark 2
Final loop: Flip 3s to 0, 2s to 1
Good point! I like your way better!
class Solution:
def gameOfLife(self, board: List[List[int]]) -> None:
"""
Do not return anything, modify board in-place instead.
0 -> 0: 0
1 -> 1: 1
0 -> 1: 2
1 -> 0: 3
"""
def count(r,c):
cnt = 0
for i in range(r-1,r+2):
for j in range(c-1,c+2):
if ((i==r and j==c) or
i==rows or j==cols or i
Basically, use new digits for values that change.
@@NeetCode just divide by 2 instead of looking for 2 or 3. Similarly you can do mod 2 to get the fist bit. In cpp i just shifted into bit 2 since it's clearer that way.
Or you could just assign each cell its value shifted by one so it will be the most significant bit (out of two):
cell >>= 1; //at least in C/JS/etc, not sure about Python
(Edit) oh, haven't noticed that Alex already mentioned it
(0 -> 1): -1
(0 -> 0): 0
(1 -> 1): 1
(1 -> 0): 2
1st loop:
if board[nei_row][nei_col] > 0: count += 1 (loop all valid direction)
if board[row][col] == 1 and (count < 2 or count > 3): board[row][col] = 2
elif board[row][col] == 0 and count == 3: board[row][col] = -1
2nd loop:
if board[row][col] == 2: board[row][col] = 0
elif board[row][col] == -1: board[row][col] = 1
I clicked like and then started watching!! :-) ... Thanks for these videos
Like it is shown in the video, we can go ahead with the mapping:
0: 0,0
1: 1,0
2: 0,1
3: 1,1
But one neat trick to check neighbouring initial alive cells, is we can just take whatever value we have and do '%2'. say, a visited cell would have been "1" when its updated cell value%2==1. (From above mapping, 1 and 3 would get "1" on "%2"). For an unvisited cell, the initial alive value would be 1 which also when you do "%1" you get 1.
Once we populate the array with new values, just do integer "/2" on all the values and you will get correct final states.
10K subscribers !!! Keep doing. Your videos will be gem to future engineers.
Woah its at 185k right now. Amazing growth man.
678k Damnnn!!!
Absolute Genius !!!! Mindblowing solution.
Java Solution:
class Solution {
public int countNeighbours(int board[][], int r, int c, int rows, int cols)
{
int cnt = 0;
for(int i = r - 1; i < r + 2 ; i++)
{
for(int j = c - 1; j < c + 2; j++)
{
if((i == r && j == c) || i < 0 || j < 0 || i >= rows || j >= cols)
continue;
if(board[i][j] == 1 || board[i][j] == 3)
cnt++;
}
}
return cnt;
}
public void gameOfLife(int[][] board) {
int rows = board.length, cols = board[0].length;
for(int i = 0; i < rows; i++)
{
for(int j = 0; j < cols; j++)
{
int cnt = countNeighbours(board, i, j, rows, cols);
if(board[i][j] >= 1 && (cnt == 2 || cnt == 3))
board[i][j] = 3;
else if(cnt == 3)
board[i][j] = 2;
}
}
for(int i = 0; i < rows; i++)
{
for(int j = 0; j < cols; j++)
{
if(board[i][j] == 1)
board[i][j] = 0;
else if(board[i][j] >= 2)
board[i][j] = 1;
}
}
}
}
I don't know whether that's really saving memory. You add an extra bit to every field instead of making a new array which kind of defeats the purpose of saving memory
Although yes if you have integers anyway might aswell do that
Would using something like 5,6,7,8 as the mapping would make it a bit easier to understand and explain to the interviewer?
This is an awesome solution !!!! Thank you so very very much !!!!!!
The ending loop body can be one line: board[r][c] = (board[r][c] >> 1) & 1
you are great sir
Thank you
Very nice explanation loved it
I did it for PCPC exam at UniSa
Really nicely explained man but why not simply map as follows:
0|0->2
1|0->3
0|1->4
1|1->5
So while checking if cell=0 OR 2 OR 4 , it means it's a dead cell cuz 2,4 were originally 0 i.e, dead AND
If cell=1 OR 3 OR 5 , it means it's a live cell cuz 3,5 were originally 1 i.e, live
AND at end when we have updated each cell , if cell=2 OR 3 make it 0 cuz 2,3 are new 0s AND if cell=4,5 make it 1 cuz 4,5 are new 1s.
Love love your vids
Sorry to hear you got covid. Hope you get better soon. btw this video is not there in your master list of coding solutions playlist.
U a God
Awesome solution!
pretty helpful. Thanks for your sharing!
this is genius!!
I had no idea you were supposed to use the original numbers, I thought you were supposed to do something insane like try to update the value, it's neighbors recursively.. which wouldn't make any sense
Cam anyone explain why when specifying the range in the count neighbours function it goes to r+2 and c+2? I thought it would only need to go +1?
What am I missing here?
for loops in python dont include the ending case. e.g for i in range(0, 10) only goes from 0-9
Because this nested loop will go through 8 directions from top left, ie. r-1, c -1 to r+1, c +1. Since python for loop doesn't count the last element, so if you want to get r + 1, you must finish range with r + 2
is this the only mapping will work or any can work?
can you please make a video on [301. Remove Invalid Parentheses] please
Hi...i have implemented Conway game of life in Python. It works very well if you draw your initial configuration "by hand" using your mouse. Now I want to implement some famous initial configuration (for example a gun or an oscillator) but I don't want to copy it using the mouse...I'm looking for a way to import the grid of a particoular configuration...do you have any idea? Thank you
save the layout of the shape using deltas (some initial middle square plus deltas in rows and cols which give us the shape). Hover the mouse around which changes the position of middle square and the deltas take care of constructing the rest of the shape. I hope I am not too vague.
Maybe I am stupid, but I was having more problem writing the logic for the countNeighbours than the core logic required to solve this problem.
Conway's game of life
Devon Conway?
contemplated using negative sign as a flag, but most likely wouldnt work.
I paused the video and couldn't find the solution... because I took the problem in a quite literal way and was representing the playing field as a bitmap. So, using 2 bits per cell is actually doubling the memory used.
Can you add a c++ video
a PhD on this problem: th-cam.com/video/FWSR_7kZuYg/w-d-xo.html&ab_channel=TheCodingTrain
6:25 How the heck 🤣🤣
Is it just me that found out that this solution does not solve the leetcode problem (typed all the code)?
Wrong Answer
Runtime: 21 ms
Case 1
Input
board =
[[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
Output
[[0,1,0],[2,0,3],[1,3,3],[0,2,0]]
Is this just being asked to talk about cellular automata?