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!!
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!
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
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.
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.
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 ?
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.
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!
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.
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 .
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.....
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
@@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.
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
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 []
@@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.
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.
To be fair, I got a full 30 minutes to write all this in a Google Doc. Still wasn't enough time, lol
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!
This question is alive and well in FAANG interviews. Was just asked it and wish I would have known the BFS && DFS trick.
I love the the small python thingies you tell in-between, thanks for that also
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!!
What a detailed explanation! You are a CZcamsr who makes people feel like a treasure！Thank you sosososo much
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!
The question I got was from Dropbox - Permissions in a file system
Sorry to hear about your experience in your interview today.
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
We all be feeling dumb doing these interviews. It is as if we never coded in our life.
But what if I want to get the coordinates (row, col) connecting the two islands?
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.
Nice idea. It should be O(n^4).
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.
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 ?
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.
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!
Neeeee(a)t explanation, visuals and code !! :) Fabulous ! Thank you.
Man this is mechanically difficult. It's basically two questions in one, DFS feeding into a layered BFS. It's good practice though.
You can add a length value in the queue, something like q.append(r,c,length+1). Return the last length as the answer.
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 .
Finally it make sense how to solve this problem and why we do all of these things, thank you
Voo thanks a lot bro, can you please cover , missing element in sorted array please
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.
LOL never mind paused there to see if I was tripping and you recognized it soon after :) great video!
Thank you so much for your solution. I have spent one hour stuck on this problem.
Beautifully explained . Thank you
Beautiful!
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.
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 .
awesome explanation man!!
always love to learn from you
I enjoy how Neetcode continues to mangle 'Dijkstra' into 'Djikstra' in every video the algorithm comes up in so far, makes him seem human.
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.....
very helpful!
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
bro how long did it take to become good at data strucutres and algos
He is born like this
@@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.
it depends on practice but atleast 400-500 questions you need to solve to achieve a good level
you're a wizard king!
code is pretty neat
Damn, what a question!
why you can use deque in leetcode without import it?
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 ??
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
I am wondering, why not just use BFS over DFS to discover the island?
Neetcode finds it easier to implement DFS recursively in general, would be same complexity 👍
I also agree it’s easier than BFS
Hi neetcode great vid as always. Can you try solving the question: All Nodes Distance K in Binary Tree next thanks
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 []
@@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.
Interesting, how do u add a par to the node, which only has left, right? I may convert it to graph instead
N = len(grid) only addresses the number of rows, shouldn't it be NR = len(grid) and NC = len(grid[0])?
it's a square grid, it was stated in the problem
What is the need of dfs in here could I not traverse the entire grid and push the values which are simply ones
no the ones can be from any island, so you can only traverse ones from one specific island
I hate coding because I don’t like having to move my fingers on the keyboard to anything that isn’t just letters 😂
Another way: O(n*k) by swelling island along the borderline.
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;
}
}
Not in love with this question. Not much logic. Just procedures. Too big to solve in JAVA
Exactly !!!
It's a pretty common question in FAANG interviews actually
NameError: name 'deque' is not defined
from collections import deque
@@spaceface2288 thabkew kind sir