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

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

[@amitupadhyay6511]

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

[@mvmalenko9132]

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

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

[@_athie2544]

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

[@sibysuriyan9980]

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

[@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!

[@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 🙂

[@infiniteloop5449]

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

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

[@clandestina_genz]

Man , this problem is absolute mind boggling

[@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?

[@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]

[@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]

[@srikid100]

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

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

[@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.

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

[@mariusy6944]

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

[@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.

[@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.

[@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?

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

[@MP-ny3ep]

Phenomenal explanation. Thank you

[@danielng8083]

Thanks!

[@NeetCode]

Thank you so much Daniel!

[@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 ? :)

[@sahejhira1346]

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

[@_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; } };

[@__________________________6910]

I played this game in my childhood.

[@martiserramolina5397]

Thank you very much!

[@begula_chan]

Thank you very much! That was really good

[@ngneerin]

Love the leetcode solutions. Looking for more such videos

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

[@decostarkumar2562]

Can we use dynamic programming?

[@krateskim4169]

Awesome explanation

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

[@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?

[@unofficialshubham9026]

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

[@muadgra3545]

Great video, as always.

[@amandwivedi1980]

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

[@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.

[@pinquisitor9552]

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

[@firezdog]

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

[@giantbush4258]

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

[@dss963]

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

[@zhgjasonVT]

Well explained! Thanks!

[@shatakshivishnoi916]

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

[@altusszawlowski4209]

Very complex

[@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.

[@shivamrawat7523]

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

[@edwardteach2]

U a Snake & Ladders God

[@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.

[@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 🤔

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

[@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?

[@sayankabir9472]

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

[@suraj8092]

He probably grew up in America

[@raunaquepatra3966]

Could have just converted the grid to a list

[@anthonydushaj3844]

Very neat !

[@atpk5651]

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

[@butoyighyslain171]

How do you even come up with this??

[@adarshsasidharan254]

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

[@RobinHistoryMystery]

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

[@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.

[@solomon8229]

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

[@Ash-fo4qs]

c++ code?

[@light_70]

great explanation

[@joeleeatwork]

Thanks!

[@NeetCode]

Thank you so much Joe!!