Max Area of Island 🧠

LeetCode Link: Max Area of Island

Difficulty: Medium

Problem Explanation 📝

Problem: LeetCode 695 - Max Area of Island

Description: Given a grid of 0's and 1's, find the maximum area of an island in the grid. An island is a group of connected 1's (horizontally or vertically). You may assume all four edges of the grid are all surrounded by water.

Intuition: To find the maximum area of an island, we can use a depth-first search (DFS) approach. The idea is to traverse the grid and whenever we encounter a land (1), we explore its neighboring cells and count the number of connected lands.

Approach:

1. Initialize a variable maxArea to store the maximum area of an island.
2. Iterate through each cell in the grid:

• If the current cell is a land (1), call the dfs function to explore its neighboring cells and update the maximum area.

3. Define a helper function dfs:

• Check if the current cell is out of bounds or is not a land (1). If so, return 0.
• Mark the current cell as visited by changing its value to 0.
• Recursively call dfs for the neighboring cells (up, down, left, right) and sum the results.

4. Return the maximum area stored in maxArea.

⌛ Time Complexity: The time complexity is O(m * n), where m is the number of rows and n is the number of columns in the grid. We visit each cell once.

💾 Space Complexity: The space complexity is O(m * n), where m is the number of rows and n is the number of columns in the grid. This is the space used for the recursion stack during the DFS traversal.

Solutions 💡

Cpp 💻

class Solution {
  public:
    int maxAreaOfIsland(vector<vector<int>> &grid) {
        if (grid.empty()) {
            return 0;
        }

        int m = grid.size();
        int n = grid[0].size();
        int maxArea = 0;

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    maxArea = max(maxArea, dfs(grid, i, j));
                }
            }
        }

        return maxArea;
    }

  private:
    int dfs(vector<vector<int>> &grid, int row, int col) {
        if (row < 0 || row >= grid.size() || col < 0 || col >= grid[0].size() || grid[row][col] == 0) {
            return 0;
        }

        grid[row][col] = 0;  // Mark the current cell as visited
        int area = 1;  // Count the current cell as part of the island
        // Recursively explore the neighboring cells (up, down, left, right)
        area += dfs(grid, row - 1, col);  // Up
        area += dfs(grid, row + 1, col);  // Down
        area += dfs(grid, row, col - 1);  // Left
        area += dfs(grid, row, col + 1);  // Right
        return area;
    }
};

Python 🐍

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        def dfs(row, col):
            if (
                row < 0
                or row >= len(grid)
                or col < 0
                or col >= len(grid[0])
                or grid[row][col] == 0
            ):
                return 0

            grid[row][col] = 0  # Mark as visited
            area = 1

            area += dfs(row + 1, col)  # Check down
            area += dfs(row - 1, col)  # Check up
            area += dfs(row, col + 1)  # Check right
            area += dfs(row, col - 1)  # Check left

            return area

        max_area = 0
        for row in range(len(grid)):
            for col in range(len(grid[0])):
                if grid[row][col] == 1:
                    max_area = max(max_area, dfs(row, col))

        return max_area