MAX AREA OF AN ISLAND | PYTHON | LEETCODE # 695

Today's we're going to be solving Leetcode Problem # 695 - Max Area of an Island. This is a relatively straightforward problem but the approach serves as a foundation for a lot of similar problems on Leetcode.

We'll be solving this with a Depth First Search approach and the coding pattern used here is very common so pay attention to the implementation details as you'll encounter many problems similar to this!

[surajthapa]

Please don't stop making these videos. Thanks!

[dnm]

Thanks a lot man! I appreciate the vids a lot!

[skyforever]

Man your explanation is so precise and easy to understand !! I am gonna be watching all your vids now : )
Keep up the good work mate !

[yashshukla]

- **Introduction**
- Problem: LeetCode #695, "Max Area of an Island"
- Importance: Common in coding interviews, basis for many similar problems.

- **Problem Explanation**
- Input: m x n binary matrix (grid)
- Island: Group of connected 1s (land) in four directions (horizontal/vertical)
- Task: Return the maximum area of an island or 0 if no island exists.

- **Example Walkthrough**
- Various island areas: 1, 4, 4, 5, 6 (maximum is 6).

- **Solution Concept**
- Use Depth-First Search (DFS)
- On finding a 1 (land):
- Search for connected land in all four directions.
- Mark visited cells as 0 to avoid revisiting.

- **DFS Implementation Details**
- Avoid infinite loops by marking visited cells.
- Use a directions list for up, down, left, right movement.
- Traverse the grid row by row and column by column.
- For each 1 found, calculate the island’s area and update the max area.

- **Edge Cases**
- Ensure bounds are checked before accessing grid indices.
- If bounds are exceeded, return 0 to avoid errors.

- **Function Explanation**
- `find_area` function:
- Checks if current cell is valid (within bounds and equals 1).
- Sets current cell to 0 to mark it as visited.
- Calculates area by recursively exploring neighboring cells.
- Returns the total area for the current island.

- **Alternative Approach**
- If modifying the input is not allowed, use a set to track visited cells.

- **Time & Space Complexity**
- Time: O(rows * columns) — must visit each cell once.
- Space:
- O(rows * columns) if recursive call stack is counted.
- O(1) if stack space is ignored (constant space for directions).

- **Conclusion**
- Depth-First Search is a common pattern in many LeetCode problems.
- Knowing this solution helps with many similar coding challenges.

[Change]

Is there any benefit of using dfs over bfs in these questions? or its the same basically?