Snakes and Ladders - Leetcode 909 - Python

[@NeetCode]

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)

[@studyaccount794]

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.

[@daringcalf]

Same here. I was gonna kill myself for stuck at this problem and Neetcode saved my life.

[@FlashLeopard700]

@@daringcalf doing the daily challenge eh? me too

[@shashwatsingh9247]

Hope you got a good one !

[@makxell]

I hope you both made it

[@studyaccount794]

Ohh I don't remember making this comment lol. Anyways, I did get a job but it's not a good one so I'm back again. I made this comment when I was in college. Good thing I had a job fresh out of the college so the hard work wasn't for nothing ig haha

[@mr6462]

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.

[@kinghanzala]

If it hadn't been for the snake, then it could have been solved I guess 🙂

[@sibysuriyan9980]

"ive never played this game" *proceeds to code the entire game perfectly*

[@danielng8083]

Thanks!

[@NeetCode]

Thank you so much Daniel!

[@amitupadhyay6511]

I was waiting for this question since 2 weeks . Its a trending question, being asked in many recent interviews and OA.

[@dinankbista5794]

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}; } }

[@mvmalenko9132]

it's crazy how you're able to break down such a complex problem into such an intuitive explanation

[@_athie2544]

Very easy to understand! Love this solution. You are the best KZbinr on solving Leetcode problems.

[@pichu8115]

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!

[@AayushVatsa]

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; } --

[@infiniteloop5449]

If we can use extra memory, the implementation of intToPos becomes way easier if we convert it to a 1D array.

[@clandestina_genz]

Man , this problem is absolute mind boggling

[@siftir2683]

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?

[@arpanbanerjee6224]

@neetcode, can you please explain this part

[@ratin754]

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

[@navaneethmkrishnan6374]

For anyone confused, that's exactly the game of snakes and ladders. You are forced to take the ladder or the snake as you go. You can't also take two ladders in a row. It's the game rules.

[@umairiqbal5172]

Exactly my question

[@umairiqbal5172]

@@navaneethmkrishnan6374you don’t understand the question. The problem is if you reach a spot via ladder and that spot has a bigger ladder you won’t be able to use it and you’ll mark it visited but what if there is another path to that spot that allows you to use the biggest ladder which

[@srikid100]

I really like all your videos ! Great explanation and easy to understand- thanks !!!

[@robogirlTinker]

Hello Mr. Neetcode, I watch your KZbin 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?

[@vidhishah9154]

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

[@jonaskhanwald566]

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

[@noormohamed8005]

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]

[@subhankarbhattacharyya8939]

We won't really need to reverse the board just one simple code addition in intToPos() function should do the trick i.e. just follow whatever was done previously with column and reverse the row right before sending the result. For ex: def intToPos(int square): row = (square-1)//length col = (square-1)%length if((row&1)!=0): col = len-1-col row = len-1-row; # This is the only change to be added in order to not reverse the board return [row, col] Let me know if this helps 😉

[@subhasisrout123]

Which part of the code prevents consecutive snakes or ladder ? This was one of the requirement.

[@altusszawlowski4209]

the fact that he doesnt have a while loop on the condition if the cell is not -1

[@gabrielfonseca1642]

The BFS goes from i to (i + 1, i + 2, ... i + 6). Since 0 is not added, the next move will never take the ladder at the same position. It can only be reached from i - 1 and below (which will be another path found by the algorithm). Note that the if statement ensures that if we try to reach position i via a dice roll, the destination gets replaced by the ladder destination.

[@YairGOW]

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).

[@daringcalf]

True. Just queue := []int{1} could do.

[@dhanrajbhosale9313]

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]

[@ngneerin]

Love the leetcode solutions. Looking for more such videos

[@MP-ny3ep]

Phenomenal explanation. Thank you

[@sahejhira1346]

but i don't understand- which instruction tells the algo to output the minimum number of moves required to reach n**2th element.

[@haritjoshi878]

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.

[@kanhakesarwani971]

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

[@alijohnnaqvi6383]

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

[@mariusy6944]

Could the board be converted into a one-dimensional array to simplify the problem and nothing else would change?

[@muadgra3545]

Great video, as always.

[@decostarkumar2562]

Can we use dynamic programming?

[@ShivamSharma-me1sv]

Can we solve this by creating a mapping from 1,2,3,4..n^2 to -1,-1,-1,-1.....? will this have worse space complexity?

[@lingyuhu4623]

what if the nextSquare is greater than length * length? Why we dont have to take that into consideration?

[@jayeshnagarkar7131]

hey bro, i have the same question.. can you please explain if you knew the answer ? :)

[@sampathkodi6052]

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?

[@altusszawlowski4209]

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

[@huizhao2050]

Hi, one question for big tech companies interview? Can I use google search in online code assessment?

[@ohyash]

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.

[@martiserramolina5397]

Thank you very much!

[@amandwivedi1980]

very nice explanation :) Keep up the good work !!!

[@__________________________6910]

I played this game in my childhood.

[@begula_chan]

Thank you very much! That was really good

[@unofficialshubham9026]

where did you take care of the case that no two snake/ladder are taken in one move

[@_nucleus]

You literally can do it without reversing with the same code, just one line change class Solution { public: pair num_to_pos(int num, int n) { int r = (num - 1) / n; int c = (num - 1) % n; if (r % 2 == 0) { return {n - 1 - r, c}; } else { return {n - 1 - r, n - 1 - c}; } } int snakesAndLadders(vector& board) { int n = board.size(); queue q; // {square, moves} q.push({1, 0}); vector visited(n, vector(n, 0)); while(!q.empty()) { auto node = q.front(); q.pop(); int square = node.first, moves = node.second; for(int mov = 1; mov n * n) continue; pair pos = num_to_pos(next_square, n); if(board[pos.first][pos.second] != -1) { next_square = board[pos.first][pos.second]; } if(next_square == n * n) return moves + 1; if(!visited[pos.first][pos.second]) { visited[pos.first][pos.second] = 1; q.push({next_square, moves + 1}); } } } return -1; } };

[@krateskim4169]

Awesome explanation

[@zhgjasonVT]

Well explained! Thanks!

[@shatakshivishnoi916]

great explanation!!..what would be complexity of this code?

[@altusszawlowski4209]

Very complex

[@shivamrawat7523]

why did you used bfs here? how could I know if I have to use bfs or dfs?

[@xiaohuisun]

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

[@rahuldwivedi4758]

What if there are two ladders in a possible move, the later being the bigger one. Why do you take the first ladder itself?

[@po-shengwang5869]

how are you sure that it's the min steps to get to the final destination?

[@surajbahuguna8560]

It's BFS so we are traversing level by level. All elements in a level can be reached in same number of moves. Any element in the next levels would require a greater number of moves. Hence the first element or the first level to reach N*N will have the minimum number of moves.

[@edwardteach2]

U a Snake & Ladders God

[@jamesmandla1192]

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

[@infiniteloop5449]

I think its the opposite case in the real game right? Otherwise why would anyone take a snake....

[@jamesmandla1192]

@@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 😂

[@srushtinarnaware4919]

thanks

[@capybarapika]

1:48 bro really said he never played Snake and Ladder. I'm shocked

[@suraj8092]

He probably grew up in America

[@LarryFisherman5]

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

[@dss963]

There is a mistake in the intopos function I guess , because for the r value it should be( length-1 ) -(square-1)//n.

[@giantbush4258]

It's easier to convert the 2D to a 1D representation

[@pinquisitor9552]

For the r,c I’d just create a dictionary v:[r,c], no need to switch rows or start from 0…

[@anthonydushaj3844]

Very neat !

[@firezdog]

I think if you did DFS it might not find the shortest path.

[@adarshsasidharan254]

the fact that you've never played Snakes and Ladders amazes me

[@justadev____7232]

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?

[@butoyighyslain171]

How do you even come up with this??

[@RobinHistoryMystery]

“A game that I never really played” , bro missed out😢 on

[@user-le6ts6ci7h]

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.

[@umairiqbal5172]

I don’t understand how the visited set doesn’t prevent us from finding the optimal solution let’s take for example the cause that you can each a certain square 13 via ladder but that prevents you from using the biggest ladder which starts at square 13 it doesn’t make sense.

[@umairiqbal5172]

One possible explanation is that there will never be a cause where a spot that can be reached with a ladder has another ladder.

[@arunraman6630]

The hardest part about this question for me was converting from Boustrophedon form. After that, it's just your bog-standard BFS

[@CostaKazistov]

Not only Boustrophedon, but a *reverse* Boustrophedon en.wikipedia.org/wiki/Boustrophedon#Reverse_boustrophedon which is an additional step 🤔

[@stormarrow2120]

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.

[@atpk5651]

Is it just me or facebook interview questions are actually kind of tricky??

[@raunaquepatra3966]

Could have just converted the grid to a list

[@solomon8229]

why use column and row. turn it into a standard list with 36 elements. no extra coding neaded

[@Ash-fo4qs]

c++ code?

[@joeleeatwork]

Thanks!

[@NeetCode]

Thank you so much Joe!!

[@light_70]

great explanation