GOOGLE'S #1 INTERVIEW QUESTION (MARCH 2022) | SHORTEST PATH IN GRID WITH OBSTACLE ELIMINATION

[@chisomedoka5651]

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

[@Taurdil]

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.

[@def__init]

Really clear explanation, love the variable names too

[@cs74546]

thank you man, what a talent! really best explanations on youtube

[@BEEFnCHEESE44]

Great explanation, thank you for sharing!

[@ramyhussein4091]

Would be highly appreciated if you can do Problem 317. Shortest Distance from All Buildings

[@crackfaang]

Just made the video. Will be uploaded next week. It's really fucking hard. Explaining it is so hard haha

[@ramyhussein4091]

@@crackfaang Thanks tons for the great efforts and brilliant explanations!

[@ebenezeracquah478]

Thanks for the video explanation.

[@isma5627]

Amazing explanation!

[@eddiej204]

Appreciated

[@christianjt7018]

Great explanation, thanks!

[@praggyav]

great explanation! thanks!!

[@subee128]

Thanks

[@papa6568671]

Really awesome !! thanks for the explanation!! this really helps me a lot, big big appreciate!!! subscribe :D!!!

[@rliu2]

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

[@kewtomrao]

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!

[@crackfaang]

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

[@varunshrivastava2706]

@@crackfaang Do you work at Google?

[@crackfaang]

@@varunshrivastava2706 I can neither confirm nor deny 😉

[@varunshrivastava2706]

@@crackfaang I guess I got my answer 😂😂

[@kevingonzalez9790]

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

[@abhiramnatarajan8093]

From first glance, you dont seem to have stored K in your queue.

[@abhiramnatarajan8093]

Also, visited and queue seem to have their values flipped.