Snakes and Ladders - Leetcode 909 - Python
Vložit
- čas přidán 9. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 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
📚 STACK PLAYLIST: • Stack Problems
Python Code: github.com/neetcode-gh/leetco...
Problem Link: leetcode.com/problems/snakes-...
0:00 - Read the problem
4:25 - Drawing Explanation
10:14 - Coding Explanation
leetcode 909
This question was identified as a facebook coding interview question from here: github.com/xizhengszhang/Leet...
#facebook #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
Python Code: github.com/neetcode-gh/leetcode/blob/main/909-Snakes-and-Ladders.py
Java Code: github.com/ndesai15/coding-java/blob/master/src/com/coding/patterns/bfs/SnakesLadders.java (from a viewer - ndesai)
I remember I used to play this game with my siblings and friends as a kid. Now, here I am. Solving this problem all alone on leetcode in a locked room in hope of getting a good job.
Same here. I was gonna kill myself for stuck at this problem and Neetcode saved my life.
@@nobiaaaa doing the daily challenge eh? me too
Hope you got a good one !
I hope you both made it
"ive never played this game"
*proceeds to code the entire game perfectly*
I was waiting for this question since 2 weeks . Its a trending question, being asked in many recent interviews and OA.
Very easy to understand! Love this solution. You are the best CZcamsr on solving Leetcode problems.
Could you make a video of teaching us how to visualise concepts or anything or introducing some materials inspiring you how to visualise things? I think it must be very useful!
I really like all your videos ! Great explanation and easy to understand- thanks !!!
Love the leetcode solutions. Looking for more such videos
Here is the java implementation:
class Solution {
public int snakesAndLadders(int[][] board) {
reverseBoard(board);
Queue queue = new LinkedList();
queue.add(1);
int steps =0;
HashSet visited = new HashSet();
visited.add(1);
while(!queue.isEmpty()){
int size = queue.size();
for (int i=0; i< size; i++){
Integer curr = queue.poll();
if (curr==board.length * board.length) return steps;
for (int j=1; j board.length * board.length) continue;
if (board[res[0]][res[1]] != -1) {
next = board[res[0]][res[1]];
}
if (!visited.contains(next)){
visited.add(next);
queue.add(next);
}
}
}
steps++;
}
return -1;
}
public void reverseBoard(int[][] board){
for (int i=0; i< board.length/2; i++){
for (int j=0; j< board[0].length; j++){
int[] temp = board[i].clone();
board[i][j] = board[board.length-1-i][j];
board[board.length-1-i][j] = temp[j];
}
}
}
public int[] coordinateConverter(int pos, int[][]board){
//O based indexing
int row = (pos-1) / board.length;
int col = (pos-1) % board.length;
if (row%2==1) {
col = board.length-1-col;
}
return new int[]{row, col};
}
}
Thanks for the great video! I am wondering if this problem can be solved using DP? I couldn't seem to find a good recursive substructure as the best steps to reach 13 may actually come from 17.
If it hadn't been for the snake, then it could have been solved I guess 🙂
Hello Mr. Neetcode,
I watch your CZcams videos and i really appreciate the way you explain. I just love it.
Can you please make video on how do you find Time complexity and Space complexity so easily?
Great video, as always.
Well explained! Thanks!
Phenomenal explanation. Thank you
very nice explanation :) Keep up the good work !!!
You can also avoid using the moves variable and just count how many levels you've gone through throughout the bfs. So just add the newly discovered nodes to an auxiliary queue, then when the main queue is empty you know you're at a new level and then the aux queue becomes the main one. This continues obviously until you reach the last node or aux and main are both empty (which means no way to reach the end goal).
True. Just queue := []int{1} could do.
If we can use extra memory, the implementation of intToPos becomes way easier if we convert it to a 1D array.
Man , this problem is absolute mind boggling
Thank you very much! That was really good
Very neat !
Thanks!
Thank you so much Daniel!
Awesome explanation
Hi,
Your explanation goes straight to head and problem becomes easily solvable. Thank you for your help to the community.
Can you please cover the leetcode problem 811 - subdomain visit count and leetcode 459 - Repeated Substring Pattern? This would be a big help.
Thanks
great explanation
Great video with super clear approach discussion but a quick doubt why you did n - c - 1 for the column? Yes I know because of the alternating fashion we will get wrong values for the column for the square or cell value, like why that n - c - 1 worked even tho it worked as this can be a good question for the interviewer to ask.
how is this BFS traversal taking care of the case when a single move contains 2 ladders? Like for this example in the video, the "15" box could have a ladder of its own that wouldn't be taken if we took the ladder at "2". How do we know that ladder wouldn't take us faster?
@neetcode, can you please explain this part
suppose you go from 2 to 15. 15 is added to q. 15 also has a ladder but you are not doing any advancement. now when 15 is popped from the q, you will either be adding 1,2,3, etc to it, never 0. so 16, 17 etc would be added to the q
I played this game in my childhood.
but i don't understand-
which instruction tells the algo to output the minimum number of moves required to reach n**2th element.
FOR CONVERTING LABEL VALUE TO CO-ORDINATES.
It will be better to create a map once with the exact structure of board rather than reversing it and doing complex maths everytime.
-- Code
private Map getCellValToCoordinateMap(int n) {
Map map = new HashMap();
boolean reverse = false;
int val = 1;
for(int r=n-1; r>=0; r--) {
if (!reverse) {
for(int c=0; c=0; c--) {
map.put(val, new Pair(r, c));
val++;
}
}
reverse = !reverse;
}
return map;
}
--
without reversing the board
def int_to_pos(self, square, n):
square = square-1
div, mod = divmod(square,n)
r = n-div-1
if (square//n)%2:
c = n-mod-1
else:
c = mod
return [r, c]
Which part of the code prevents consecutive snakes or ladder ? This was one of the requirement.
the fact that he doesnt have a while loop on the condition if the cell is not -1
Hi, one question for big tech companies interview? Can I use google search in online code assessment?
Depends on the assessment. Most of them allow you to use google. Very few don't.
You'll know in the assessment instructions itself about this. Read that before starting the assessment.
Can we use dynamic programming?
U a Snake & Ladders God
thanks
One edge case missed, if from the current position we can reach at end, we do not need to put it as (moves+1). We can stop our algorithm there.
The test case for it is: [[-1,-1,-1],[-1,9,8],[-1,8,9]]
Updated code:
class Solution:
def snakesAndLadders(self, board: List[List[int]]) -> int:
n = len(board)
board.reverse()
def intToPos(square):
r = (square-1)//n
c = (square-1) %n
if r%2: # odd
c = n-1-c
return [r,c]
moves_collected = []
def bfs():
visited = set()
q = []
q.append([1,0])
while q:
square,moves = q.pop(0)
for i in range(1,7):
nextMove = square+i
if nextMove
we are exploring every possible value from lets say from x + 1 to x + 6 for each x which gives an intution as it was a backtracking problem exploring all the possible path until reached n^^2. Is it correct or am I missing something?
possibly, backtracking would give you all paths to n^2 and then you would need to find the min from all those paths, bfs allows you to break an return once you find the shortest path
should not add a square to the visited if that square is reached by a shortcut, since that square could have a shortcut itself, and could make a quick move if reached by a normal move
Here's a C++ implementation of the approach discussed above.
I am facing problem in a test case: [[-1,-1,-1],[-1,9,8],[-1,8,9]]
Please help.
class Solution {
public:
vector intToPos(int square, int n){
int r = (square-1)/n;
int c = (square-1)%n;
if(r%2)
c = n-1-c;
vector pos;
pos.emplace_back(r);
pos.emplace_back(c);
return pos;
}
int snakesAndLadders(vector& board) {
int n = board.size();
reverse(board.begin(),board.end());
queue q;
q.push({1,0});
unordered_set visited;
while(!q.empty())
{
pair curr = q.front();
q.pop();
int square = curr.first;
int moves = curr.second;
for(int i=1;i
What if there are two ladders in a possible move, the later being the bigger one. Why do you take the first ladder itself?
where did you take care of the case that no two snake/ladder are taken in one move
why did you used bfs here? how could I know if I have to use bfs or dfs?
great explanation!!..what would be complexity of this code?
Very complex
what if the nextSquare is greater than length * length? Why we dont have to take that into consideration?
hey bro, i have the same question.. can you please explain if you knew the answer ? :)
“A game that I never really played” , bro missed out😢 on
For the r,c I’d just create a dictionary v:[r,c], no need to switch rows or start from 0…
It's easier to convert the 2D to a 1D representation
I think if you did DFS it might not find the shortest path.
1:48 bro really said he never played Snake and Ladder. I'm shocked
He probably grew up in America
There is a mistake in the intopos function I guess , because for the r value it should be( length-1 ) -(square-1)//n.
you can make the hardest part easy by just converting the grid into an array like this:
(If direction is negative, append the rows in reverse order)
dir = 1
a = [0]
n = len(board)
for i in range(n-1,-1,-1):
if dir>0: a.extend(board[i])
else: a.extend(board[i][::-1])
dir*=-1
I had a small change to it. So that we can access it using row and column. If there any advantage by converting it a single array, how will i access the values?
b = []
a = [0]
d = 1
n = len(board)
for i in range(n-1, -1,-1):
if d > 0 :
a.extend(board[i])
b.append(a)
else :
a.extend(board[i][::-1])
b.append(a)
d = d * -1
a = [0]
Simpler version of intToPos without reversing the board:
n = len(board)
def int_to_pos(idx):
i = ~(idx // n)
j = idx % n if i % 2 else ~(idx % n)
return i, j
the fact that you've never played Snakes and Ladders amazes me
I didn't know in Snakes and Ladders if you moved past a snake/ladder you didn't actually have to take it. So I over-complicated the problem a lot LOL
I think its the opposite case in the real game right? Otherwise why would anyone take a snake....
@@infiniteloop5449 you’re right, I worded what I said earlier poorly. I meant if your dice roll moves your piece to a position after the snake/ladder it means u move to that position directly instead of taking the snake/ladder first. I guess that’s how it works in most board games though 😂
Could have just converted the grid to a list
If somebody seeing this take a note of this test case ,
[[-1,1,1,1],[-1,7,1,1],[16,1,1,1],[-1,1,9,1]]. How come there is an answer to this. it must be -1 ,but leetcode is expecting 3.
The hardest part about this question for me was converting from Boustrophedon form. After that, it's just your bog-standard BFS
Not only Boustrophedon, but a *reverse* Boustrophedon
en.wikipedia.org/wiki/Boustrophedon#Reverse_boustrophedon which is an additional step 🤔
How do we know how far the snake takes you? You stated when we reach 17, the snake takes us to 13. Why not 15 or 14?
yeah the heck eith that r,c transformation.. yuck
as a design standpoint. it would be so much more intuitive to just keep track of this game in a 1D array.
Is it just me or facebook interview questions are actually kind of tricky??
c++ code?
why use column and row. turn it into a standard list with 36 elements. no extra coding neaded
Thanks!
Thank you so much Joe!!