Shortest Bridge - Leetcode 934 - Python

[@shoooozzzz]

This question is alive and well in FAANG interviews. Was just asked it and wish I would have known the BFS && DFS trick.

[@vincentmarquez3096]

This is one of those "the algorithm is easy but lets see if you can write ~50 loc bug free in ten minutes" kind of tests.

[@shoooozzzz]

To be fair, I got a full 30 minutes to write all this in a Google Doc. Still wasn't enough time, lol

[@mertkahyaoglu48]

I was just trying to solve this and came here to check whether you uploaded a video for this. Surprised that you just uploaded man, thanks a lot!

[@yukselpolatakbyk8468]

I started watching you 6 months ago. Today I tried this by myself before checking your solution and I realized that I had the right idea just couldn't figure out minor bugs. If it wasn't for your videos I would have no idea how to even approach this. Thanks again!!

[@sahilkulria7325]

I love the the small python thingies you tell in-between, thanks for that also

[@an4220]

I'm grateful to get a teacher like you...

[@xiomoen3943]

What a detailed explanation! You are a KZbinr who makes people feel like a treasure！Thank you sosososo much

[@b9944236]

When I understand the key point is DFS(a very basic island problem) + BFS (a very basic shortest path), then I can solve this problem by myself. Thanks a lot.

[@sidazhong2019]

You can add a length value in the queue, something like q.append(r,c,length+1). Return the last length as the answer.

[@anarsalami9906]

Great explanation, as always! When I search to look explanation of any of the coding problem, first I am trying to find if you have any video for that question before looking at different videos. Thanks a lot.

[@АлександрЯрулин-й7и]

Thanks. Comment: the more safe 'def invalid' will be r < 0 or c < 0 or r > N - 1 or c > N - 1 . Not r == N, c == N .

[@halahmilksheikh]

Man this is mechanically difficult. It's basically two questions in one, DFS feeding into a layered BFS. It's good practice though.

[@cosmicgirl910]

I had an interview today and legit almost cried bc I was so stuck and helpless. I studied leetcode but the question required me to implement a class, which you never have to do in leetcode. Could you solve problems where you would implement a class to solve the problem please? Thanks!

[@cosmicgirl910]

The question I got was from Dropbox - Permissions in a file system

[@yang5843]

Sorry to hear about your experience in your interview today.

[@Eisae]

That's unfortunate, sure you'll crush your next interview. Do you have a link to this or a similar question? Kinda interested in what exactly you had to do

[@SmoothCode]

We all be feeling dumb doing these interviews. It is as if we never coded in our life.

[@AnkitaNallana]

So, I'm familiar with dfs/bfs but for the newbs, i think an intuition as to why bfs with the visited set would've been good to provide. For me, it was easy to visualize how a visited set would help, but I think more explanation there would've been good!

[@curesnow6493]

Thank you so much for your solution. I have spent one hour stuck on this problem.

[@Krblshna]

Finally it make sense how to solve this problem and why we do all of these things, thank you

[@vicnetc5964]

Would it be possible to go through every 1 in the first island and find its distance to the second island. For example, for the 1 at (1,0), we would find that its distance to the second island is 4. We can find this by first determining the coordinates of the second island (4,2), (4,3), and (4,4) and then using the equation x2-x1 + y2-y1. So we would have 4-1+2-0 = 5 as the smallest raw value, and then we subtract 1 to get 4 (because we only need to connect the islands). We could do this for every single point on the first island and find the minimum of the values to get the distance. I'm not sure if this would be more or less efficient than the approach you explained, but in the solution I described, you wouldn't need to look at any of the 0's in the array.

[@ygwg6145]

Nice idea. It should be O(n^4).

[@nakshayachaudhary]

Here is what I used : I actually used DFS to find all cells of both islands, then whichever cell which has a single opening to water, I added it to an array.....This way I had 2 arrays containing boundary cells of both islands. Now to find no. of cells needed to connect any 2 cells is abs(r1-r2) + abs(c1-c2) -1, I just the found the minimum possible value for the expression and voila....you have the answer.....

[@aloksahu1457]

As usual the best explanation . Thanks much for these videos. Any thoughts if there are n islands and we need to create a bridge connecting all of them in a shortest path ?

[@vdyb745]

Neeeee(a)t explanation, visuals and code !! :) Fabulous ! Thank you.

[@remixowlz]

But what if I want to get the coordinates (row, col) connecting the two islands?

[@Shameer..]

Think I found a small mistake, @ 4:26 Since it's 4-directionally connected, graph[3][2] should not be 1 so numbers in the bottom right 3x2 should all be +1. Didn't change the solution in this example tho.

[@Shameer..]

LOL never mind paused there to see if I was tripping and you recognized it soon after :) great video!

[@sirmidor]

I enjoy how Neetcode continues to mangle 'Dijkstra' into 'Djikstra' in every video the algorithm comes up in so far, makes him seem human.

[@MP-ny3ep]

Beautifully explained . Thank you

[@pranavsharma7479]

Voo thanks a lot bro, can you please cover , missing element in sorted array please

[@vijethkashyap151]

Beautiful!

[@pulkitk3388]

awesome explanation man!!

[@tusharsharma7069]

always love to learn from you

[@dr_drone]

you're a wizard king!

[@allandogreat]

code is pretty neat

[@CommandantNOVA]

On line 20, is the sole point of this loop just to keep res from being incremented early? Because i is not used anywhere else.

[@pleasedontsubscribeme4397]

yeah, 'i' is used to traverse layer by layer, so that after first layer points are visited, res gets incremented by 1 and we move on to process the next layer of coordinates if queue is not empty, hence the while loop .

[@cc-to2jn]

intresting! I did it a very similer way but differ syntax style. Unlike you I looked for the initial starting edges for island 1 and then did the bfs. q=deque() visited=set() def findEdge(i,j): if (i

[@ramankr0022]

very helpful!

[@allandogreat]

why you can use deque in leetcode without import it?

[@rajastylez]

I am wondering, why not just use BFS over DFS to discover the island?

[@def__init]

Neetcode finds it easier to implement DFS recursively in general, would be same complexity 👍 I also agree it’s easier than BFS

[@fdk9913]

Hi neetcode great vid as always. Can you try solving the question: All Nodes Distance K in Binary Tree next thanks

[@yukselpolatakbyk8468]

Hi, Here is a solution I found 6 months ago. I hope it helps. It is easy once you understand the idea: class Solution: def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]: #mark the parent of every node def dfs(node, par = None): if node: node.par = par dfs(node.left, node) dfs(node.right, node) dfs(root) queue = deque([(target, 0)]) #node, dist seen = {target} while queue: if queue[0][1] == k: #once we see one d ==2 it means everything else in q is also that level return [node.val for node, d in queue] node, d = queue.popleft() #add every neig of node with new level for nei in (node.left, node.right, node.par): if nei and nei not in seen: seen.add(nei) queue.append((nei, d+1)) return []

[@fdk9913]

@@yukselpolatakbyk8468 hi thanks for that. I ended up searching that question and saw a similar code. I actually get it now. The thing that was bothering me was how was i meant to get the previous nodes, but a hash map makes so much sense.

[@shensean1784]

Interesting, how do u add a par to the node, which only has left, right? I may convert it to graph instead

[@linchuantian623]

Hey I have a confusion about this question how do I guaranteed that the result will be the minimum path that connects the two island ??

[@bryananananana]

We are using BFS to explore the water layer by layer, so the first land tile we encounter (not in visited) must be the shortest path from the other island

[@calvinklein5223]

N = len(grid) only addresses the number of rows, shouldn't it be NR = len(grid) and NC = len(grid[0])?

[@faithcyril513]

it's a square grid, it was stated in the problem

[@Mohammedllt]

Damn, what a question!

[@pranavyeleti3499]

bro how long did it take to become good at data strucutres and algos

[@pseudounknow5559]

He is born like this

[@alphabee8171]

@@pseudounknow5559 i promise you people spend lifetimes finding out one of these algorithms and some even didn't reach that point. They are born with determination for sure, practice and repeat is the only answer.

[@baap6886]

it depends on practice but atleast 400-500 questions you need to solve to achieve a good level

[@cheeseborger3758]

I hate coding because I don’t like having to move my fingers on the keyboard to anything that isn’t just letters 😂

[@ygwg6145]

Another way: O(n*k) by swelling island along the borderline.

[@mr.unknown4124]

Why are these problems so difficult. My brain is hurting. Maybe some people are born genius..

[@valivetiswamynagasainivas6167]

What is the need of dfs in here could I not traverse the entire grid and push the values which are simply ones

[@whitesaladchips]

no the ones can be from any island, so you can only traverse ones from one specific island

[@ChinmayAnaokar-xm4ci]

C# Implemenation public class Solution { readonly int[][] directions = new int[][] { new int[] { 0, 1 }, new int[] { 0, -1 }, new int[] { 1, 0 }, new int[] { -1, 0 } }; HashSet visited = new HashSet(); public int ShortestBridge(int[][] grid) { Queue q = new Queue(); for (int i = 0; i < grid.Length; i++) { for (int j = 0; j < grid[0].Length; j++) { if (grid[i][j] == 1) { DFS(grid, i, j, q); return BFS(grid, q); } } } return -1; } private void DFS(int[][] grid, int row, int col, Queue q) { if (row < 0 || row >= grid.Length || col < 0 || col >= grid[0].Length || visited.Contains((row, col)) || grid[row][col] != 1) { return; } visited.Add((row,col)); q.Enqueue((row, col)); dfs(grid, row - 1, col, q); dfs(grid, row, col + 1, q); dfs(grid, row + 1, col, q); dfs(grid, row, col - 1, q); return; } private int BFS(int[][] grid, Queue q) { int res= 0; while (q.Any()) { int size = q.Count; while (size > 0) { var row_col = q.Dequeue(); foreach(int[] dir in directions) { int r = dir[0] + row_col.R; int c = dir[1] + row_col.C; if (r >= grid.Length || r < 0 || c >= grid[0].Length || c < 0 || visited.Contains((r, c))) { continue; } if (grid[r][c] == 1) { return level; } else { visited.Add((r, c)); q.Enqueue((r, c)); } } size--; } res+= 1; } return res; } }

[@remixowlz]

NameError: name 'deque' is not defined

[@spaceface2288]

from collections import deque

[@remixowlz]

@@spaceface2288 thabkew kind sir

[@asheeshpathak1497]

Not in love with this question. Not much logic. Just procedures. Too big to solve in JAVA

[@pseudounknow5559]

Exactly !!!

[@jamesmandla1192]

It's a pretty common question in FAANG interviews actually