695. Max Area of Island

MediumDepth-First SearchBreadth-First SearchUnion FindArrayMatrix
Leetcode Link

Problem Description

In the given LeetCode problem, we are provided with a 2D grid of 0s and 1s, where each 1 represents a piece of land, and 0s represent water. The grid represents a map where islands are formed by connecting adjacent 1s horizontally or vertically. We need to determine the size of the largest island in the grid, with the island's size being the count of 1s that make up the island. If no islands are present in the grid, the result should be 0.

An example grid might look like this:

11 1 0 0 0
21 1 0 0 0
30 0 1 0 0
40 0 0 1 1

In this grid, there are three islands with sizes 4, 1, and 2, respectively. The goal is to return the size of the largest island, which would be 4 in this case.

Intuition

To solve this problem, we can use Depth-First Search (DFS) to explore each piece of land (1) and count its area. We iterate through each cell of the grid; when we encounter a 1, we start a DFS traversal from that cell. As we visit each 1, we mark it as visited by setting it to 0 to ensure that each land cell is counted only once. This also helps to avoid infinite loops.

The DFS algorithm explores the land in all four directions: up, down, left, and right. For each new land cell we find, we add 1 to the area of the current island and recursively continue the search from that new cell. Once we can't explore further (we hit 0s, or we reach the grid's boundaries), the recursive calls will return the total area of that particular island to the initial call.

By performing DFS on each 1 we find, we can calculate the area of each island. We keep track of the maximum area encountered during these searches. Once we've processed the whole grid, we have the largest island's area captured, and we return this as our result.

Learn more about Depth-First Search, Breadth-First Search and Union Find patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Solution Approach

The solution uses Depth-First Search (DFS), a classical algorithm for exploring all elements in a connected component of a grid, graph, or network. In this scenario, "connected components" are the individual islands within the grid.

The implementation consists of:

  1. A helper function, dfs, which is a recursive function that takes the row and column indices (i, j) of a point in the grid as arguments.
  2. Within dfs, we first check if the current cell contains a 1. If it contains a 0, it's either water or already visited, so we return an area of 0 for that cell.
  3. If the current cell is a 1, we initiate the area of this part of the island with 1, and then set the cell to 0 to mark it as visited.
  4. We define the possible directions we can explore from the current cell using the array dirs which contains the relative movements to visit top, right, bottom, and left adjacent cells.
  5. We loop through each direction and calculate the new coordinates (x, y) for the adjacent cells. For each adjacent cell that is within the boundaries of the grid, we recursively call dfs.
  6. The recursive dfs calls will return the area of the connected 1s, which we add to the area of the current island.
  7. After exploring all directions, the total area of the island, including the current cell, is returned.

At the top level of the maxAreaOfIsland function:

  1. We get the number of rows m and columns n of the grid.
  2. Then, we initiate a comprehensive search across all cells in the grid using list comprehension together with max function. Here, we only start a dfs traversal when we find a 1 (land cell).
  3. Whichever cell starts a new DFS, the area of the connected island will be calculated completely before moving on to the next cell in the comprehension.
  4. Finally, the maximum area found during the DFS traversals is returned.

By marking visited cells and only initiating DFS on unvisited land cells, we ensure that each islandโ€™s area is calculated once, which gives us the efficiency and correctness of the algorithm.

This pattern of search and marking is common in problems dealing with connected components in a grid and is a handy technique to remember for similar problems.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of these pictures shows the visit order of a depth-first search?

Example Walkthrough

Letโ€™s illustrate the solution approach with a small example. Consider the following 2D grid:

10 1
21 0

In this grid, there are two islands, each consisting of a single piece of land (1). We aim to find the size of the largest island, although in this case, as both islands are of size 1, the result should be 1.

  1. Begin by initializing maxArea to 0. This variable will keep track of the largest island area found.
  2. The algorithm starts scanning the grid from the top-left cell. When it encounters a 1, it performs a DFS from that cell.
  3. Let's start with the cell at (0,1). Since it's a land cell (1), we call the dfs function.
  4. Inside dfs, we set the current cell to 0 to mark it visited and initialize the area to 1, since we already found one piece of land.
  5. The dfs function will check all adjacent cells (in our case, there is only one at (1,0)) and perform dfs on them if they are part of the land (if they contain 1).
  6. The dfs function is called on cell (1,0). Again, it will set the cell to 0, increment the area to 2, and check surrounding cells.
  7. Since the adjacent cells are either water (0) or out of bounds, there are no further recursive calls, and the total area for this island is 1.
  8. We return to the top level of the maxAreaOfIsland function and continue checking the next cells. Since all 1s have been visited, there are no new DFS calls.
  9. The maxArea of 1 found is the size of the largest island, which is returned.

In this example, the algorithm correctly identifies the size of the largest island in the grid, which is 1, and demonstrates the typical flow of search using DFS in this context.

Solution Implementation

1class Solution:
2    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
3        def dfs(row: int, col: int) -> int:
4            # If the current cell is water (0), return area 0
5            if grid[row][col] == 0:
6                return 0
7          
8            # Current cell is land, so mark it as visited by setting it to 0,
9            # and start area count at 1 (for the current cell)
10            area = 1
11            grid[row][col] = 0
12          
13            # Directions for exploring neighboring cells: up, right, down, left
14            directions = (-1, 0, 1, 0, -1)
15          
16            # Iterate over the (row, col) pairs of neighboring cells
17            for delta_row, delta_col in zip(directions, directions[1:]):
18                next_row, next_col = row + delta_row, col + delta_col
19              
20                # Check if the neighboring cell is within bounds and not visited
21                if 0 <= next_row < row_count and 0 <= next_col < col_count:
22                    # Increase the area count by the area of the neighboring island part
23                    area += dfs(next_row, next_col)
24          
25            # Return the total area found for this island
26            return area
27
28        # Get the dimensions of the grid
29        row_count, col_count = len(grid), len(grid[0])
30      
31        # Use a list comprehension to apply DFS on each cell of the grid
32        # Only cells with value 1 (land) will contribute to the area
33        max_area = max(dfs(row, col) for row in range(row_count) for col in range(col_count) if grid[row][col] == 1)
34      
35        # Return the maximum area found among all islands
36        return max_area
37
1public class Solution {
2    private int rows;            // Number of rows in the grid
3    private int cols;            // Number of columns in the grid
4    private int[][] grid;        // The grid itself
5
6    public int maxAreaOfIsland(int[][] grid) {
7        rows = grid.length;             // Set the total number of rows in the grid
8        cols = grid[0].length;          // Set the total number of columns in the grid
9        this.grid = grid;               // Assign the input grid to the instance variable
10        int maxArea = 0;                // To keep track of the maximum area found so far
11
12        // Iterate over every cell in the grid
13        for (int i = 0; i < rows; ++i) {
14            for (int j = 0; j < cols; ++j) {
15                // Update the maximum area after performing DFS on current cell
16                maxArea = Math.max(maxArea, dfs(i, j));
17            }
18        }
19        return maxArea;                 // Return the maximum area found
20    }
21
22    // Helper method to perform Depth-First Search (DFS)
23    private int dfs(int row, int col) {
24        // If the current cell is water (0), or it is already visited, then the area is 0
25        if (grid[row][col] == 0) {
26            return 0;
27        }
28
29        int area = 1;                    // Start with a size of 1 for the current land cell
30        grid[row][col] = 0;              // Mark the land cell as visited by sinking it (set to 0)
31        int[] dirs = {-1, 0, 1, 0, -1};  // Array to represent the four directions (up, right, down, left)
32
33        // Iterate over the four directions
34        for (int k = 0; k < 4; ++k) {
35            int nextRow = row + dirs[k];      // Calculate the row for adjacent cell
36            int nextCol = col + dirs[k + 1];  // Calculate the column for adjacent cell
37
38            // Check if adjacent cell is within the bounds and then perform DFS
39            if (nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols) {
40                area += dfs(nextRow, nextCol); // Add the area found from DFS to the total area
41            }
42        }
43        return area;                      // Return the total area found from the current cell
44    }
45}
46
1#include <vector>
2#include <functional> // For std::function
3#include <algorithm>  // For std::max
4
5class Solution {
6public:
7    // Function to find the maximum area of an island in a given grid
8    int maxAreaOfIsland(std::vector<std::vector<int>>& grid) {
9        // Obtain the number of rows and columns of the grid
10        int rows = grid.size(), cols = grid[0].size();
11        // Directions array to explore all 4 neighbors (up, right, down, left)
12        int directions[5] = {-1, 0, 1, 0, -1};
13        // Variable to store the final maximum area of island found
14        int maxArea = 0;
15      
16        // Depth-first search function using lambda and std::function for ease of recursion
17        std::function<int(int, int)> depthFirstSearch = [&](int i, int j) -> int {
18            // Base case: if the current cell is water (0), return 0 area
19            if (grid[i][j] == 0) {
20                return 0;
21            }
22          
23            // Mark the current cell as visited by setting it to 0 and start counting the area from 1
24            int area = 1;
25            grid[i][j] = 0;
26          
27            // Explore all 4 neighbor directions
28            for (int k = 0; k < 4; ++k) {
29                int x = i + directions[k], y = j + directions[k + 1];
30                // Check if the neighbor coordinates are within grid bounds
31                if (x >= 0 && x < rows && y >= 0 && y < cols) {
32                    // Increment the area based on this recursive depth-first search
33                    area += depthFirstSearch(x, y);
34                }
35            }
36            // Return the area found for this island
37            return area;
38        };
39      
40        // Iterate over all cells in the grid
41        for (int i = 0; i < rows; ++i) {
42            for (int j = 0; j < cols; ++j) {
43                // Update maxArea with the maximum between current maxArea and newly found area
44                maxArea = std::max(maxArea, depthFirstSearch(i, j));
45            }
46        }
47      
48        // Return the maximum area of island found in the grid
49        return maxArea;
50    }
51};
52
1function maxAreaOfIsland(grid: number[][]): number {
2    const rows = grid.length;
3    const cols = grid[0].length;
4    // Define the directions for exploring adjacent cells (up, right, down, left)
5    const directions = [-1, 0, 1, 0, -1];
6  
7    // Helper function to perform DFS and calculate the area of the island
8    const exploreIsland = (row: number, col: number): number => {
9        if (grid[row][col] === 0) {
10            // If the current cell is water (0), then there's no island to explore
11            return 0;
12        }
13
14        // Initialize area for the current island
15        let area = 1;
16        // Mark the current cell as visited by setting it to water (0)
17        grid[row][col] = 0;
18        // Explore all adjacent cells
19        for (let k = 0; k < 4; ++k) {
20            const nextRow = row + directions[k];
21            const nextCol = col + directions[k + 1];
22            if (nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols) {
23                // Increment the area by the area of adjacent lands
24                area += exploreIsland(nextRow, nextCol);
25            }
26        }
27        return area;
28    };
29
30    // Initialize maximum area of an island to be 0
31    let maxArea = 0;
32    // Loop through every cell in the grid
33    for (let row = 0; row < rows; ++row) {
34        for (let col = 0; col < cols; ++col) {
35            // Update the maxArea if a larger island is found
36            maxArea = Math.max(maxArea, exploreIsland(row, col));
37        }
38    }
39    // Return the maximum area of an island found in the grid
40    return maxArea;
41}
42
Not Sure What to Study? Take the 2-min Quiz๏ผš

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Time and Space Complexity

Time Complexity

The time complexity of the algorithm is O(M * N), where M is the number of rows and N is the number of columns in the grid. This is because in the worst case, the entire grid could be filled with land (1's), and we would need to explore every cell exactly once. The function dfs is called for each cell, but each cell is flipped to 0 once visited to avoid revisiting, ensuring each cell is processed only once.

Space Complexity

The space complexity is O(M * N) in the worst case, due to the call stack size in the case of a deep recursion caused by a large contiguous island. This would happen if the grid is filled with land (1's) and we start the depth-first search from one corner of the grid, the recursion would reach the maximum depth equal to the number of cells in the grid before it begins to unwind.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Recommended Readings

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

DSU/Union Find Fundamentals

Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ