So I followed his advice, watched his shortest path in binary matrix video, understood his solution, and I coded this one completely myself (in 33mins) I’m so proud of myself, I didn’t have to watch this video. Thank you so much sir
Feels like just doing simple BFS 0..K times might be a bit more efficient (esp. if K could be pretty big, we can do binary search instead of just incrementing K) due to abrupt BFS termination in cases where there is no path for current K.
Hi, I tried another way myself but doesn't seem to work. My dp doesn't seem to work properly. What am I doing wrong here? class Solution: def shortestPath(self, grid: List[List[int]], k: int) -> int: m, n = len(grid), len(grid[0]) if k >= m + n - 2: return m + n - 2 dp = {} dir = [(1, 0), (0, 1), (-1, 0), (0, -1)] visit = set() def dfs(x0, y0, k0): if k0 < 0: return float('inf') if x0 == m-1 and y0 == n-1: return 0 if (x0, y0, k0) in dp: return dp[(x0, y0, k0)] visit.add((x0, y0)) res = float('inf') for xd, yd in dir: x1, y1 = x0 + xd, y0 + yd if x1 in range(m) and y1 in range(n) and (x1, y1) not in visit: newRes = (dfs(x1, y1, k0-1) if grid[x1][y1] == 1 else dfs(x1, y1, k0)) res = min(res, newRes + 1) visit.remove((x0, y0)) dp[(x0, y0, k0)] = res return res res = dfs(0, 0, k) return res if res != float('inf') else -1 I tried removing dp, which makes it 'correct' but still can't pass previous test cases due to time complexity issue
This channel is great! Its slowly gaining momentum. Ig you should promote the channel on linkedin? Also if you could make a video on how we could improve leetcode contest ratings, it would be helpful!
Haha I can’t promote it on LinkedIn because I don’t want to give away my name and identity (probably get fired). Also I have never done a leetcode contest as I think they’re a complete waste of time. Perhaps if you solve these questions as a hobby but for me I always focused on the company I wanted and didn’t bother with anything else. Stay focused on the goal
So I followed his advice, watched his shortest path in binary matrix video, understood his solution, and I coded this one completely myself (in 33mins) I’m so proud of myself, I didn’t have to watch this video. Thank you so much sir
Feels like just doing simple BFS 0..K times might be a bit more efficient (esp. if K could be pretty big, we can do binary search instead of just incrementing K) due to abrupt BFS termination in cases where there is no path for current K.
thank you man, what a talent! really best explanations on youtube
Really clear explanation, love the variable names too
Thanks for the video explanation.
Great explanation, thank you for sharing!
Great explanation, thanks!
Amazing explanation!
great explanation! thanks!!
Would be highly appreciated if you can do Problem 317. Shortest Distance from All Buildings
Just made the video. Will be uploaded next week. It's really fucking hard. Explaining it is so hard haha
@@crackfaang Thanks tons for the great efforts and brilliant explanations!
Appreciated
Thanks
Really awesome !! thanks for the explanation!! this really helps me a lot, big big appreciate!!!
subscribe :D!!!
Hi, I tried another way myself but doesn't seem to work. My dp doesn't seem to work properly. What am I doing wrong here?
class Solution:
def shortestPath(self, grid: List[List[int]], k: int) -> int:
m, n = len(grid), len(grid[0])
if k >= m + n - 2:
return m + n - 2
dp = {}
dir = [(1, 0), (0, 1), (-1, 0), (0, -1)]
visit = set()
def dfs(x0, y0, k0):
if k0 < 0:
return float('inf')
if x0 == m-1 and y0 == n-1:
return 0
if (x0, y0, k0) in dp:
return dp[(x0, y0, k0)]
visit.add((x0, y0))
res = float('inf')
for xd, yd in dir:
x1, y1 = x0 + xd, y0 + yd
if x1 in range(m) and y1 in range(n) and (x1, y1) not in visit:
newRes = (dfs(x1, y1, k0-1) if grid[x1][y1] == 1
else dfs(x1, y1, k0))
res = min(res, newRes + 1)
visit.remove((x0, y0))
dp[(x0, y0, k0)] = res
return res
res = dfs(0, 0, k)
return res if res != float('inf') else -1
I tried removing dp, which makes it 'correct' but still can't pass previous test cases due to time complexity issue
where am I going wrong?
var shortestPath = function(grid, k) {
const queue = [ [0, 0, 0] ];
const visited = new Set([ 0 + ',' + 0 ]);
const rows = grid.length, cols = grid[0].length;
while (queue.length > 0) {
const [ row, col, distance ] = queue.shift();
if (row === rows - 1 && col === cols - 1) return distance;
const deltas = [[1, 0], [-1, 0], [0, 1], [0, -1]];
for (let delta of deltas) {
const [deltaRow, deltaCol] = delta;
const neighborRow = row + deltaRow;
const neighborCol = col + deltaCol;
const neighborPos = neighborRow + ',' + neighborCol;
const rowInbounds = 0
From first glance, you dont seem to have stored K in your queue.
Also, visited and queue seem to have their values flipped.
This channel is great!
Its slowly gaining momentum.
Ig you should promote the channel on linkedin?
Also if you could make a video on how we could improve leetcode contest ratings, it would be helpful!
Haha I can’t promote it on LinkedIn because I don’t want to give away my name and identity (probably get fired).
Also I have never done a leetcode contest as I think they’re a complete waste of time. Perhaps if you solve these questions as a hobby but for me I always focused on the company I wanted and didn’t bother with anything else. Stay focused on the goal
@@crackfaang Do you work at Google?
@@varunshrivastava2706 I can neither confirm nor deny 😉
@@crackfaang I guess I got my answer 😂😂