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.
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
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; } --
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!
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.
Hello Mr. Neetcode, I watch your RU-vid 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?
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
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]
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]
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?
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
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.
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
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
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).
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.
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.
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
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
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
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.
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.
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.
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.
@@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 😂
