Hey NeetCode, just wanted to say thank you for these videos. You do an awesome job at explaining your thought process and how you think about/approach these problems. They've really helped me in my preparation for my interviews. I ended up landing several FAANG offers and a lot of that is due to the content that you provide! Thank you again!
Solution using BFS: class Solution: def maxAreaOfIsland(self, grid: List[List[int]]) -> int: maxAreaSoFar = 0 visited = set() rows = len(grid) cols = len(grid[0]) def bfs(i,j): visited.add((i,j)) q = collections.deque() q.append((i,j)) directions = [[1,0], [-1,0], [0,1], [0,-1]] islandArea = 1 while q: r, c = q.popleft() for dr,dc in directions: row = r + dr col = c + dc if (row in range(rows) and col in range(cols) and grid[row][col] == 1 and (row, col) not in visited): islandArea += 1 visited.add((row, col)) q.append((row, col)) return islandArea for i in range(rows): for j in range(cols): if grid[i][j] == 1 and (i,j) not in visited: maxAreaSoFar = max(maxAreaSoFar, bfs(i,j)) return maxAreaSoFar
Python BFS Code: ROW, COL = len(grid), len(grid[0]) MAX_ISLAND_AREA = 0 def bfs(r, c): q = deque([]) q.append((r, c)) grid[r][c] = 0 area = 0 while q: r, c = q.popleft() area+=1 directions = [[0, 1], [1, 0], [-1, 0], [0, -1]] for dr, dc in directions: nr, nc = r + dr, c + dc if min(nr, nc) >= 0 and nr < ROW and nc < COL and grid[nr][nc] == 1: q.append((nr, nc)) grid[nr][nc] = 0 return area for row in range(ROW): for col in range(COL): if grid[row][col] == 1: MAX_ISLAND_AREA = max(MAX_ISLAND_AREA, bfs(row , col)) return MAX_ISLAND_AREA
we can remove the usage of set by doing , when we visit a cell having 1 just replace it to 2 or any value other than 1 then in the base case just check if the current cell is not 1 then return 0
Hey @NeetCode, First you said it's similar to LC200 Number of Islands and there you used BFS, not DFS. I wonder why is that and what did you mean by similar in this case? I used slightly modified version of LC200 BFS in this problem and it worked fine, also ran quicker than 150ms and it seems to be more straight forward solution for me to be honest (this is a matter of opinion though). Cheers!
Definitely easier to remember the Number of Islands solution and just modify the bfs to sum the area with each iteration the code above...Particularly in the context of Neetcode where Max Area of Island comes one or two after Number of Islands.
@@raghavbhat especially since we don't need either of the specific functionalities of bfs or dfs, just need a way to iteratively explore a matrix without making a decision at every point
Great video! As a small addition - the space complexity could be improved if instead of setting each visited cell into Set data structure you just change the value of the visited cell to 0. This way even visiting it second time it's already counted. Also, it could be solved iteratively, using stack.
I'd put a check of grid[r][c] == 1 in line 18 as you did in num of islands to just skip a full matrix of 0 all together. OFC same big O, but less runtime in general.
//C++ Code //Algorithm Used: DFS //Concept: Just as we count number of island, in this case when converting 1 to 0 we will also count the number of time we did that and after every return fron the DFS function we will assign max with the max value amongst what max already has and what temp has become and finally return the answer. void DFS(int i,int j,vector &grid,int &temp){ if(i==-1 || j==-1 || i==grid.size() || j==grid[0].size() || grid[i][j]==0) return; if(grid[i][j]==1){ temp++; grid[i][j]=0; DFS(i+1,j,grid,temp); DFS(i-1,j,grid,temp); DFS(i,j+1,grid,temp); DFS(i,j-1,grid,temp); } } int maxAreaOfIsland(vector& grid) { int ans=0; for(int i=0;i
Heres a BFS I came up with(only came up with this cause of following your channel,.. you are goated) class Solution: def maxAreaOfIsland(self, grid: List[List[int]]) -> int: if not grid: return 0 rows = len(grid) cols = len(grid[0]) visit = set() q = collections.deque() def bfs(r, c): visit.add((r, c)) q.append((r, c)) directions = [[1, 0], [-1, 0], [0, -1], [0, 1]] curr_area = 0 while q: row, col = q.popleft() curr_area += 1 for dr, dc in directions: r = row + dr c = col + dc if(r in range(rows) and c in range(cols) and (r, c) not in visit and grid[r][c] == 1): q.append((r, c)) visit.add((r, c)) return curr_area area = 0 for r in range(rows): for c in range(cols): if (r, c) not in visit and grid[r][c] == 1: val = bfs(r, c) area = max(area, val) return area
Instead of using hashmap for visited land we can just change the value of visited land from '1' to '2' So that way code will use less space and also by doing this you won't have to check if the land is visited or not
I don't think there's a need to use another data structure to mark the visited nodes, just make them equal to any other arbitrary value other than 0,1 say 2 and that shall do it.
Hi NeetCode, in a real interview I was explaining this solution. I was questioned the time complexity and said O(mxn). But he mentioned that in case of hash collision the complexity is N. My question to you is shall we not consider is as O(1) or O(n)? TIA
Average case is O(1), but when a collision happens, we could argue that it's O(N) because it might be iterating through a linked list at that index to find the value (also known as chaining).
Quick Question: How does this solution differentiate to count Spaces that have "1" vs "0" . In the Number of island problems you had this check? @NeetCode
If you don't mind modifying the input, you can simply mark the visited cells with 0 instead of using a hash set. Leetcode still accepted my submission with that strategy.
Suppose i have an unsorted list [1,8,86,34,77,18,98,16] how can i find the two closest integers with constant time . I'm not using any sort function..only hash..can anyone help me ?
If we can convert only one 0 of our choice to 1, then how can we find the max area of land? Brute soln will take O((m×n)×(m×n)) How can we optimize it to O(m×n) ?
if that element in the grid is already visited you don't want to run dfs on it again as it is already computed and will increase the time complexity. And once calculated it won't add up to the area right? So in that case we return 0. Hope it helps!
Poras was right, and I tried removing the visit set portion and got RuntimeError for maximum recursion depth exceeded. So by having a visit set, it's improving our time complexity.
I have solved this question using the same code as your no. of islands video (using bsf), It works ! class Solution: def maxAreaOfIsland(self, grid: List[List[int]]) -> int: if not grid: return 0 rows = len(grid) cols = len(grid[0]) maxArea = 0 visited = set() # bfs function def bfs(r, c): nonlocal maxArea area = 1 queue = collections.deque() visited.add((r,c)) queue.append((r,c)) while queue: for _ in range(len(queue)): row, col = queue.popleft() directions = [[1,0], [-1,0], [0, -1], [0 , 1]] for dr, dc in directions: if ((dr + row) in range(rows) and (dc + col) in range(cols) and grid[dr + row][dc + col] == 1 and (dr + row, dc + col) not in visited): visited.add((dr + row, dc + col)) queue.append((dr + row, dc + col)) area += 1 maxArea = max(maxArea , area)
#for each and every position , call bfs for i in range(rows): for j in range(cols): if (i,j) not in visited and grid[i][j] == 1: bfs(i , j) return maxArea
Recursive way: Code might be seems to be big but it is just a DRY code. class Solution: def maxAreaOfIsland(self, grid: List[List[int]]) -> int: visited_islands = set() res = 0 before = 0 def recursive(r, c): # check the top if r > 0 and grid[r - 1][c]==1 and ((r-1, c)) not in visited_islands: visited_islands.add((r - 1, c)) recursive(r - 1, c) # check the bottom if r < len(grid) - 1 and grid[r + 1][c]==1 and ((r+1, c)) not in visited_islands: visited_islands.add((r + 1, c)) recursive(r + 1, c) # check the left if c > 0 and grid[r][c - 1]==1 and ((r, c-1)) not in visited_islands: visited_islands.add((r, c - 1)) recursive(r, c - 1) # check the right if c < len(grid[0]) - 1 and grid[r][c + 1]==1 and ((r, c+1)) not in visited_islands: visited_islands.add((r, c + 1)) recursive(r, c + 1)
for r in range(len(grid)): for c in range(len(grid[0])): print(r, c) if grid[r][c] == 1 and (r, c) not in visited_islands: visited_islands.add((r, c)) recursive(r, c) res = max(res, len(visited_islands) - before) before = len(visited_islands) #res = max(res, recursive(r, c, 0)) return res
![Lp. Сердце Вселенной #60 РОЖДЕНИЕ ЛОЛОЛОШКИ [Финал] • Майнкрафт](http://i.ytimg.com/vi/YoR0pAV9FVQ/mqdefault.jpg)
🚀 neetcode.io/ - A free resource to prepare for Coding Interviews
Hey NeetCode, just wanted to say thank you for these videos. You do an awesome job at explaining your thought process and how you think about/approach these problems. They've really helped me in my preparation for my interviews. I ended up landing several FAANG offers and a lot of that is due to the content that you provide! Thank you again!
That's awesome Travis, happy I could help!!
Nice work. If I dare ask, how'd you get a foot in the door with recruiters for FAANGs?
@@Deschuttes thanks! Some of them reached out on LinkedIn and others I just applied through their openings.
Solution using BFS:
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
maxAreaSoFar = 0
visited = set()
rows = len(grid)
cols = len(grid[0])
def bfs(i,j):
visited.add((i,j))
q = collections.deque()
q.append((i,j))
directions = [[1,0], [-1,0], [0,1], [0,-1]]
islandArea = 1
while q:
r, c = q.popleft()
for dr,dc in directions:
row = r + dr
col = c + dc
if (row in range(rows) and
col in range(cols) and
grid[row][col] == 1 and (row, col) not in visited):
islandArea += 1
visited.add((row, col))
q.append((row, col))
return islandArea
for i in range(rows):
for j in range(cols):
if grid[i][j] == 1 and (i,j) not in visited:
maxAreaSoFar = max(maxAreaSoFar, bfs(i,j))
return maxAreaSoFar
Python BFS Code:
ROW, COL = len(grid), len(grid[0])
MAX_ISLAND_AREA = 0
def bfs(r, c):
q = deque([])
q.append((r, c))
grid[r][c] = 0
area = 0
while q:
r, c = q.popleft()
area+=1
directions = [[0, 1], [1, 0], [-1, 0], [0, -1]]
for dr, dc in directions:
nr, nc = r + dr, c + dc
if min(nr, nc) >= 0 and nr < ROW and nc < COL and grid[nr][nc] == 1:
q.append((nr, nc))
grid[nr][nc] = 0
return area
for row in range(ROW):
for col in range(COL):
if grid[row][col] == 1:
MAX_ISLAND_AREA = max(MAX_ISLAND_AREA, bfs(row , col))
return MAX_ISLAND_AREA
we can remove the usage of set by doing , when we visit a cell having 1 just replace it to 2 or any value other than 1 then in the base case just check if the current cell is not 1 then return 0
instead of 2 just set it to 0. We are anyways not visiting 0 and already have a base case defined for it.
Thank you, I am studying to become and SDE and this is very helpful in clarifying things for a noob.
thanks for uploading, please continue to update your playlist as i usually go back and forth with your playlist
Excellent explanation, straightforward solution. Thanks.
Question: why you have not chosen bfs and the iterative approach?
Besides setting the cell as zero on the grid, you can also do the DFS in a while loop with a list, to save the recursion overhead.
Instead of calling dfs() for every (r,c) , we could instead invoke the function only when grid[r][c]==1.
There's a variant from FB where you're allowed to flip one ocean tile to land, and then find the max area of the new island
Please let me know where I can find the question or the solution for it
Hey @NeetCode,
First you said it's similar to LC200 Number of Islands and there you used BFS, not DFS. I wonder why is that and what did you mean by similar in this case? I used slightly modified version of LC200 BFS in this problem and it worked fine, also ran quicker than 150ms and it seems to be more straight forward solution for me to be honest (this is a matter of opinion though). Cheers!
Dfs and bfs are almost the same, and in this problem can be used interchangeably
Definitely easier to remember the Number of Islands solution and just modify the bfs to sum the area with each iteration the code above...Particularly in the context of Neetcode where Max Area of Island comes one or two after Number of Islands.
@@raghavbhat especially since we don't need either of the specific functionalities of bfs or dfs, just need a way to iteratively explore a matrix without making a decision at every point
The code of NeetCode is very neat and understandable.
Done thanks
Trivial, same as number of islands problem but keep track of largest island
Idk what kind of words could express my gratefulness. You’re doing the God’s job as they said :) thank you again
Great video!
As a small addition - the space complexity could be improved if instead of setting each visited cell into Set data structure you just change the value of the visited cell to 0. This way even visiting it second time it's already counted.
Also, it could be solved iteratively, using stack.
Your videos have been so helpful for me. Thank you!
Thank you. I could solve the problem by myself less than 15min using the same approach.
A great solution. Instead of keeping visit set, we can just set that position to 0 so we know its already visited.
I'd put a check of grid[r][c] == 1 in line 18 as you did in num of islands to just skip a full matrix of 0 all together. OFC same big O, but less runtime in general.
Thanks @NeetCode I tried without using visit set, awesome explanation.
class Solution {
public int maxAreaOfIsland(int[][] grid) {
int rows = grid.length, cols = grid[0].length;
int area = 0;
for(int i=0; i= cols || grid[x][y] == 0) return 0;
grid[x][y] = 0;
return 1 + dfs(x+1, y, grid) + dfs(x-1, y, grid) + dfs(x, y+1, grid) + dfs(x, y-1, grid);
}
}
you can skip the set part by using 0 as visited, and override the grid[i][j] = 0 so it is considered visited
Hey. Thanks for the solution. How would you replace the "for" loops with a recursive solution? I have a similar problem to solve but no loops allowed.
Beautiful solution. Appreciate everything you do!
Very explicit explanation. Thank you so much!
//C++ Code
//Algorithm Used: DFS
//Concept: Just as we count number of island, in this case when converting 1 to 0 we will also count the number of time we did that and after every return fron the DFS function we will assign max with the max value amongst what max already has and what temp has become and finally return the answer.
void DFS(int i,int j,vector &grid,int &temp){
if(i==-1 || j==-1 || i==grid.size() || j==grid[0].size() || grid[i][j]==0) return;
if(grid[i][j]==1){
temp++;
grid[i][j]=0;
DFS(i+1,j,grid,temp);
DFS(i-1,j,grid,temp);
DFS(i,j+1,grid,temp);
DFS(i,j-1,grid,temp);
}
}
int maxAreaOfIsland(vector& grid) {
int ans=0;
for(int i=0;i
best channel I've ever seen ! I appreciate it 💫
Love your matrix solutions!
Heres a BFS I came up with(only came up with this cause of following your channel,.. you are goated)
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
if not grid:
return 0
rows = len(grid)
cols = len(grid[0])
visit = set()
q = collections.deque()
def bfs(r, c):
visit.add((r, c))
q.append((r, c))
directions = [[1, 0], [-1, 0], [0, -1], [0, 1]]
curr_area = 0
while q:
row, col = q.popleft()
curr_area += 1
for dr, dc in directions:
r = row + dr
c = col + dc
if(r in range(rows) and c in range(cols) and
(r, c) not in visit and grid[r][c] == 1):
q.append((r, c))
visit.add((r, c))
return curr_area
area = 0
for r in range(rows):
for c in range(cols):
if (r, c) not in visit and grid[r][c] == 1:
val = bfs(r, c)
area = max(area, val)
return area
Bro , u are a god .
Instead of using hashmap for visited land we can just change the value of visited land from '1' to '2'
So that way code will use less space and also by doing this you won't have to check if the land is visited or not
he mentions that at the end bro
Note for myself: Ask the interviewer if we can modify the array instead of extra visit set.
Why did we use BFS for the number of islands problem but DFS for this problem??
same question
BFS can also be applied here. There is really no advantage between one another in terms of complexity.
Using DFS looks more concise in my opinion
variety
I don't think there's a need to use another data structure to mark the visited nodes, just make them equal to any other arbitrary value other than 0,1 say 2 and that shall do it.
Hi NeetCode, in a real interview I was explaining this solution. I was questioned the time complexity and said O(mxn). But he mentioned that in case of hash collision the complexity is N. My question to you is shall we not consider is as O(1) or O(n)?
TIA
Average case is O(1), but when a collision happens, we could argue that it's O(N) because it might be iterating through a linked list at that index to find the value (also known as chaining).
could you add a condition to check if grid[r][[c] == 1 in the bottom nested loop to optimize it?
Amazing video
Quick Question: How does this solution differentiate to count Spaces that have "1" vs "0" . In the Number of island problems you had this check? @NeetCode
Have you tried doing it that way? Wondering the same
Just tried it, it works that way as well!
Thanks!@@videowatcher4852
I think you missed `+` between the all dfs calls.
return 1 + dfs(r+1, c) + dfs(r-1, c) + dfs(r, c+1) + dfs(r, c-1)
If you don't mind modifying the input, you can simply mark the visited cells with 0 instead of using a hash set. Leetcode still accepted my submission with that strategy.
Suppose i have an unsorted list [1,8,86,34,77,18,98,16] how can i find the two closest integers with constant time .
I'm not using any sort function..only hash..can anyone help me ?
Not possible in O(1)
I think the best approach would be to use heap.
Using BFS is much easier though like it has no recursion lol
and has the same time complexity too
shouldn't we add a
if (r,c) in visited: continue
in the last double for loop? he said that in the explanation but didnt add it to the code
How do we solve this if we are also allowed to change the order of the columns?
see todays problem.
If we can convert only one 0 of our choice to 1, then how can we find the max area of land?
Brute soln will take O((m×n)×(m×n))
How can we optimize it to O(m×n) ?
Thanks for the video, but i don't get why this one is in the Graph category on your website🥴
why (r, c) is in visit set, we have to return 0?
if that element in the grid is already visited you don't want to run dfs on it again as it is already computed and will increase the time complexity. And once calculated it won't add up to the area right? So in that case we return 0.
Hope it helps!
Poras was right, and I tried removing the visit set portion and got RuntimeError for maximum recursion depth exceeded. So by having a visit set, it's improving our time complexity.
🔥🔥🔥
Why is this problem considered a "Graph" problem when we don't actually use a graph to solve it?
I thought dfs will give me MaximumRecursionDepth Error in Python.
set the visited island to 0 and only visit the cell with value 1
😍😍
I have solved this question using the same code as your no. of islands video (using bsf), It works !
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
if not grid:
return 0
rows = len(grid)
cols = len(grid[0])
maxArea = 0
visited = set()
# bfs function
def bfs(r, c):
nonlocal maxArea
area = 1
queue = collections.deque()
visited.add((r,c))
queue.append((r,c))
while queue:
for _ in range(len(queue)):
row, col = queue.popleft()
directions = [[1,0], [-1,0], [0, -1], [0 , 1]]
for dr, dc in directions:
if ((dr + row) in range(rows) and
(dc + col) in range(cols) and
grid[dr + row][dc + col] == 1 and
(dr + row, dc + col) not in visited):
visited.add((dr + row, dc + col))
queue.append((dr + row, dc + col))
area += 1
maxArea = max(maxArea , area)
#for each and every position , call bfs
for i in range(rows):
for j in range(cols):
if (i,j) not in visited and grid[i][j] == 1:
bfs(i , j)
return maxArea
Recursive way: Code might be seems to be big but it is just a DRY code.
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
visited_islands = set()
res = 0
before = 0
def recursive(r, c):
# check the top
if r > 0 and grid[r - 1][c]==1 and ((r-1, c)) not in visited_islands:
visited_islands.add((r - 1, c))
recursive(r - 1, c)
# check the bottom
if r < len(grid) - 1 and grid[r + 1][c]==1 and ((r+1, c)) not in visited_islands:
visited_islands.add((r + 1, c))
recursive(r + 1, c)
# check the left
if c > 0 and grid[r][c - 1]==1 and ((r, c-1)) not in visited_islands:
visited_islands.add((r, c - 1))
recursive(r, c - 1)
# check the right
if c < len(grid[0]) - 1 and grid[r][c + 1]==1 and ((r, c+1)) not in visited_islands:
visited_islands.add((r, c + 1))
recursive(r, c + 1)
for r in range(len(grid)):
for c in range(len(grid[0])):
print(r, c)
if grid[r][c] == 1 and (r, c) not in visited_islands:
visited_islands.add((r, c))
recursive(r, c)
res = max(res, len(visited_islands) - before)
before = len(visited_islands)
#res = max(res, recursive(r, c, 0))
return res