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

In this video we are solving Google's #1 interview question (at the time of recording in March 2022). Despite being a hard level question, it is actually quite simple and follows a very familiar BFS through a matrix/grid pattern that we see in so many other Leetcode problems.

[@praggyav]

great explanation! thanks!!

[@BEEFnCHEESE44]

Great explanation, thank you for sharing!

[@ebenezeracquah478]

Thanks for the video explanation.

[@def__init]

Really clear explanation, love the variable names too

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

[@isma5627]

Amazing explanation!

[@eddiej204]

Appreciated

[@subee128]

Thanks

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

[@papa6568671]

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

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

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