Game of Life - Leetcode 289 - Python
Vložit
- čas přidán 5. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
💡 BINARY SEARCH PLAYLIST: • Binary Search
Problem Link: leetcode.com/problems/game-of...
0:00 - Read the problem
4:10 - Drawing Explanation
12:21 - Coding Explanation
leetcode 289
This question was identified as a amazon interview question from here: github.com/xizhengszhang/Leet...
#game #life #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
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 ! 😀
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
No.1 leetcode tutorial! someone who actually can explain the problem and solution very clearly. Good job and keep up good work
I clicked like and then started watching!! :-) ... Thanks for these videos
This is an awesome solution !!!! Thank you so very very much !!!!!!
pretty helpful. Thanks for your sharing!
10K subscribers !!! Keep doing. Your videos will be gem to future engineers.
Woah its at 185k right now. Amazing growth man.
678k Damnnn!!!
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.
Very nice explanation loved it
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.
Awesome solution!
is this the only mapping will work or any can work?
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;
}
}
}
}
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
you are great sir
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.
Would using something like 5,6,7,8 as the mapping would make it a bit easier to understand and explain to the interviewer?
Thank you
this is genius!!
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
The ending loop body can be one line: board[r][c] = (board[r][c] >> 1) & 1
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.
U a God
can you please make a video on [301. Remove Invalid Parentheses] please
(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
6:25 How the heck 🤣🤣
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
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.
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
Conway's game of life
Devon Conway?
contemplated using negative sign as a flag, but most likely wouldnt work.
Is this just being asked to talk about cellular automata?
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]]