Max Area of Island - Leetcode 695 - Python

Показать описание

0:00 - Read the problem
1:45 - Drawing Explanation
6:18 - Coding Explanation

leetcode 695

#facebook #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

NeetCode

Рекомендации по теме

Комментарии

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!

travisc

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

LeetJourney

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

DJSTEVE

Thank you, I am studying to become and SDE and this is very helpful in clarifying things for a noob.

milo_andrs

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

ravishankardas

thanks for uploading, please continue to update your playlist as i usually go back and forth with your playlist

stanleychukwu

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!

Gameplay-psub

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.

alexandremarangonicosta

Instead of calling dfs() for every (r, c), we could instead invoke the function only when grid[r][c]==1.

md_pedia

Excellent explanation, straightforward solution. Thanks.

Question: why you have not chosen bfs and the iterative approach?

asifchoudhuryca

Thank you. I could solve the problem by myself less than 15min using the same approach.

IK-xkex

Done thanks
Trivial, same as number of islands problem but keep track of largest island

mostinho

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.

stepler