Sliding Puzzle - Leetcode 773 - Python

[@satyajit_2003]

Morning Routine: Wake up. Try to solve POTD. Solved? Go to sleep. Can't Solve? Wait for NC video. Solved. Go to sleep again.

[@NeetCodeIO]

had to whip out the red shirt

[@satyadheeraj6081]

red floral shirt 🛐

[@winkypoop]

Ooohhh just realized the shirt color represents the problem’s difficulty 😍

[@onlyforcc7]

😂

[@jody4210]

you know what im just gonna add this problem to my list and maybe one day i will come back to this

[@oldmajor5240]

For this problem the composite functions: list(map(list,board)) and tuple(map(tuple,board)) come in handy (if you don't want to flatten the matrix). Another interesting part of this problem is that half of the states are actually not solvable. You can use a parity argument and precompute the inversions in O((n+m)^2) time or O((n+m)log(n+m)) and if it isn't solvable return -1 immediately. You'd still have the worst case time complexity tho for if it is solvable.

[@JamesBond-mq7pd]

i understood concept. but still somethow it was superhard to implement

[@xieandy]

Wouldnt it be (m*n)!

[@yashwantmoharil5892]

M and n are fixed

[@joemiller4431]

Hey! I just got accepted to Amazon as an SDE, and your videos were a huge help throughout my preparation. Thanks for all the effort you put into them-keep up the awesome work!

[@akshayreddy749]

Congrats on your offer @joemiller4431, can you please tell me a bit about your prep. Thank you

[@ceciljoel9577]

Imagine how difficult codeforces would be💀

[@Ayush37262]

Wdm?

[@arunitbaidya6118]

fantastic video!😃

[@business_central]

Our savior. Thank you!

[@marcoaraujo9446]

Nice approach 👌🏻

[@noobzerg1990]

Hey I noticed in your 1d dynamic programming list on neetcode you have quite a few questions which either require 2d dynamic programming and/or 2 pointers. Where the optimal (or even close to optimal solutions) aren’t actually dynamic programming. This kinda throws me off because I read the question and either think 2 pointer or 2d dynamic programming but since I’m trying to follow the roadmap I go with the 1d dp solution against my own intuition and get a really poor solution. Is it possible you can maybe move some of these questions out of 1d dynamic programming and into 2d or 2 pointer? Palindromic substrings and partition equal subset sum (this question does have a 1d solution but it requires 2 1d arrays and even you list 2/4 solutions having 2d arrays). Unless I’m misunderstanding the definition of 1dimensional dynamic programming which is a 1d array for “memorizing” previous solutions?

[@SD-vk3ko]

Salute 🙇‍♀

[@TheGt520490]

can someone explain why dfs can't work here?

[@mygosity]

DFS can work but it is slower because it will most likely exhaust an inefficient path before it finds the fastest path. DFS can't really invalidate other seen paths without comparing how many moves it took to get to a previously seen path and then discarding it only if the new path is faster. BFS doesn't have to care about this condition because it is handling the order of paths from the shortest moves possible, so the first solution found = answer. In Javascript, BFS averages 20-50ms, DFS in 400-800ms for the current test set.

[@unlucky-777]

BFS = O(V+E) DFS = O(V!) it would be 720! which wont compile TLE I think

[@jp-wi8xr]

I too went down the same road and couldn't figure out why. The way I coded, was it stopped if it reached the end config or all possible config were visited. And all possible config = 6! = 720. So, I guess DFS would permute between all possible board configs, which would be O(720!), which is why it was TLE. Of course O(720!) is overestimated, as given a config, not all board configs are reachable. My code: class Solution: def recurse(self, board, i, j, visited): key = tuple(ele for row in board for ele in row) if key == (1, 2, 3, 4, 5, 0): return 0 if key in visited: return math.inf visited.add(key) ans = math.inf if i + 1 < 2: board[i+1][j], board[i][j] = board[i][j], board[i+1][j] ans = min(ans, 1 + self.recurse(board, i+1, j, visited)) board[i+1][j], board[i][j] = board[i][j], board[i+1][j] if i - 1 >= 0: board[i-1][j], board[i][j] = board[i][j], board[i-1][j] ans = min(ans, 1 + self.recurse(board, i-1, j, visited)) board[i-1][j], board[i][j] = board[i][j], board[i-1][j] if j + 1 < 3: board[i][j+1], board[i][j] = board[i][j], board[i][j+1] ans = min(ans, 1 + self.recurse(board, i, j+1, visited)) board[i][j+1], board[i][j] = board[i][j], board[i][j+1] if j - 1 >= 0: board[i][j-1], board[i][j] = board[i][j], board[i][j-1] ans = min(ans, 1 + self.recurse(board, i, j-1, visited)) board[i][j-1], board[i][j] = board[i][j], board[i][j-1] visited.remove(key) return ans def get_0_pos(self, board): i = j = 0 flag = False for r in range(2): if flag: break for c in range(3): if board[r][c] == 0: i = r j = c flag = True break return i, j def slidingPuzzle(self, board: List[List[int]]) -> int: i, j = self.get_0_pos(board) ans = self.recurse(board, i, j, set()) return ans if ans != math.inf else -1

[@mygosity]

@@jp-wi8xr @unlucky-777 here's a working solution in python for DFS. I also put BFS in here so you can swap between the two to see the speed difference. The key to solving this with DFS is using a cache of best times seen. class Solution: def slidingPuzzle(self, board: List[List[int]]) -> int: from collections import deque final_state = "1|2|3|4|5|0" def get_value_at_coordinate(state, x, y): #trick to converting a 2d coordinate to a flat index (x + y * columns where columns is fixed to 3 here) index = x + y * 3 return int(state[index * 2]) def set_state_at_coordinate(state, x, y, val): next_state = state.split('|') index = x + y * 3 next_state[index] = str(val) return '|'.join(next_state) board_state = '|'.join('|'.join(map(str, row)) for row in board) directions = [ (0, 1), (0, -1), (-1, 0), (1, 0) ] def bfs(state, x, y): visited = set() queue = [(state, x, y, 0)] while queue: new_queue = [] for cs, cx, cy, move in queue: if cs == final_state: return move if cs in visited: continue visited.add(cs) for dx, dy in directions: nx, ny = cx + dx, cy + dy if ny < 0 or ny >= len(board) or nx < 0 or nx >= len(board[0]): continue # Swap these positions and process next_value = get_value_at_coordinate(cs, nx, ny) next_state = set_state_at_coordinate(cs, nx, ny, 0) next_state = set_state_at_coordinate(next_state, cx, cy, next_value) new_queue.append((next_state, nx, ny, move + 1)) queue = new_queue return -1 def dfs(state, x, y): best = float('inf') visited = {} def search(cs, cx, cy, move): nonlocal best if cs in visited and move >= visited[cs]: return if cs == final_state: best = min(best, move) return visited[cs] = move for dx, dy in directions: nx, ny = cx + dx, cy + dy if ny < 0 or ny >= len(board) or nx < 0 or nx >= len(board[0]): continue # Swap these positions and process next_value = get_value_at_coordinate(cs, nx, ny) next_state = set_state_at_coordinate(cs, nx, ny, 0) next_state = set_state_at_coordinate(next_state, cx, cy, next_value) search(next_state, nx, ny, move + 1) search(state, x, y, 0) return -1 if best == float('inf') else best for y in range(len(board)): for x in range(len(board[y])): if board[y][x] == 0: return dfs(board_state, x, y) return -1

[@muskanmall4401]

why did you convert it to string? why didnt you just keep it as an array?

[@I.II..III...IIIII.....]

Any tips on how to come to think about BFS here?

[@mohamedsayed8697]

Solve BFS problems while mindfully analyzing the types of problems you use BFS. There are different types of problems that use BFS. Some use it for shortest path. Some use it for exploring a data structure like a Graph or a Tree. Some use it to explore all possibilities in level order. Think about it in this way, if you visualize all possible decisions that you take, it will form a tree, that's why BFS is used here to explore that tree in level-order fashion. So, when you notice that the problem requires you to explore all possibilities and find min path to a valid outcome of all possibilities like here, you can use BFS. I recommend you checking out these problems that can be solved the same way: Minimum Genetic Mutation, Word Ladder, and Jump Game III.

[@Cheng-EnChung]

Just wondering, why Leetcode estimate my time complexity in O(1) time? I solve it using the BFS concept from you. I consider it to be O(n) where n is the size of the 2d array

[@pastori2672]

first i thought it was a trick problem that had an obvious pattern, took a bit to realize there isnt one so i thought the size of the input is extremely small so a brute force wouldnt be bad at all, tried dfs, kinda complicated, then decided to try bfs instead and got it

[@devmahad]

thanks :)

[@giuseppeambrosio555]

when you say (n+m) I don't get how you generalize the problem. Because if you mean m row and n cols I think the number of all possible states are (n*m)! Right? If not why? I don't get it :/

[@sunithakumari333]

being 1st to comment feels good 😂

[@MargaretTurner-n8q]

I really appreciate your efforts! Could you help me with something unrelated: I have a SafePal wallet with USDT, and I have the seed phrase. (alarm fetch churn bridge exercise tape speak race clerk couch crater letter). Could you explain how to move them to Binance?

[@randheerkumargautam6433]

neat explanation of neetcode

[@ben94_]

Kinda wish i didnt read the hint this time

[@jackmax2150]

too difficult for me, i need AI help me solve this