Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Solution: Biggest Island

Problem Statement

Given a 2D array (i.e., a matrix) containing only 1s (land) and 0s (water), find the biggest island in it. Write a function to return the area of the biggest island. 

An island is a connected set of 1s (land) and is surrounded by either an edge or 0s (water). Each cell is considered connected to other cells horizontally or vertically (not diagonally).

Example 1

Input: matrix =

Image

Output: 5
Explanation: The matrix has three islands. The biggest island has 5 cells .

Image

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 50
  • matrix[i][j] is '0' or '1'.

Solution

The question follows the Island pattern and is quite similar to Number of Islands problem.

We will traverse the matrix linearly to find islands.

Whenever we find a cell with the value '1' (i.e., land), we have found an island. Using that cell as the root node, we will perform a Depth First Search (DFS) or Breadth First Search (BFS) to find all of its connected land cells. During our DFS or BFS traversal, we will find and mark all the horizontally and vertically connected land cells. 

We will keep a variable to remember the max area of any island.

Step-by-step Algorithm

Here is the detailed walkthrough of the DFS algorithm:

  1. We first initialize biggestIslandArea to 0. This variable will keep track of the largest island's area we have encountered so far.
  2. Then, we traverse each cell in the matrix. If the cell's value is 1 (land), we begin a DFS search from this cell using the visitIslandDFS function. This function will visit the cell and all its neighboring cells that are part of the same island.
  3. In the visitIslandDFS function, we first check if the current cell (x, y) is within the boundaries of the matrix and if it's a land cell. If it's not, we return 0.
  4. We then mark the current cell as visited by setting its value to 0 (water). This helps avoid visiting the same cell again and ending up in an infinite loop.
  5. We initialize the area of the current island to 1 (counting the current cell), and then add to it the areas returned by the recursive DFS calls for the neighboring cells (top, bottom, left, and right).
  6. After we finish the DFS for a cell (meaning we have visited all cells in the island that the cell is a part of), we update biggestIslandArea with the maximum of its current value and the area of the island we just finished exploring.
  7. Finally, after traversing all cells in the matrix, we return biggestIslandArea, which now holds the area of the largest island.

Here is the visual representation of the algorithm:

Image
Biggest Island

Code  (DFS)

Here is what our DFS algorithm will look like. We will update the input matrix to mark nodes visited.

Python3
Python3
. . . .

Time Complexity
Time complexity of the above algorithm will be O(M*N), where ‘M’ is the number of rows and 'N' is the number of columns of the input matrix. This is due to the fact that we have to traverse the whole matrix to find islands.

Space Complexity
DFS recursion stack can go M*N deep when the whole matrix is filled with '1's. Hence, the space complexity will be O(M*N), where ‘M’ is the number of rows and 'N' is the number of columns of the input matrix.

An Alternate Approach (Using BFS)

To find the area of the biggest island in a given 2D grid using Breadth-First Search (BFS), we traverse the grid and perform BFS on each unvisited land cell (1). During BFS, we explore all connected land cells in all four directions (right, down, left, up) and calculate the area of the island. We keep track of the largest island area encountered during the traversal.

Step-by-Step Algorithm

  1. Initialization:

    • Define a method maxAreaOfIsland that takes a 2D grid as input.
    • Initialize maxArea to 0.
    • Get the number of rows and columns in the grid.
    • Define an array directions for moving in the four possible directions (right, down, left, up).

  2. Grid Traversal:

    • Loop through each cell in the grid using nested for-loops:
      • For each cell at position (i, j), if the cell contains 1 (indicating land), call the BFS method bfs and update maxArea with the maximum value between maxArea and the result of bfs.

  3. BFS Implementation:

    • Define a method bfs that takes the grid, the starting row and column, and the directions array as input.
    • Initialize a queue for BFS and add the starting cell (row, col) to the queue.
    • Mark the starting cell as visited by setting it to 0.
    • Initialize area to 0 to keep track of the island area.
    • While the queue is not empty:
      • Dequeue a cell (currentRow, currentCol) and increment the area by 1.
      • For each direction in directions:
        • Calculate the new row and column positions.
        • If the new position is within bounds and the cell contains 1, add the cell to the queue and mark it as visited by setting it to 0.
    • Return the computed area.

  4. Return Result:

    • After traversing the entire grid, return maxArea.

Algorithm Walkthrough

Example Input:

{
    { 1, 1, 1, 0, 0 },
    { 0, 1, 0, 0, 1 },
    { 0, 0, 1, 1, 0 },
    { 0, 1, 1, 0, 0 },
    { 0, 0, 1, 0, 0 }
}

  1. Initialization:

    • maxArea is set to 0.
    • rows is 5, cols is 5.
    • directions is {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}.

  2. Grid Traversal:

    • Start at cell (0, 0), which contains 1. Call bfs with (0, 0).

  3. BFS from (0, 0):

    • Initialize queue with (0, 0).
    • Mark (0, 0) as visited (grid[0][0] = 0).
    • Initialize area to 0.

  4. First Iteration of BFS:

    • Dequeue (0, 0), increment area to 1.
    • Explore neighbors:
      • Right: (0, 1) -> Valid, add to queue, mark visited (grid[0][1] = 0).
      • Down: (1, 0) -> Valid, but contains 0.
      • Left: (0, -1) -> Invalid (out of bounds).
      • Up: (-1, 0) -> Invalid (out of bounds).
    • Queue: [(0, 1)].

  5. Second Iteration of BFS:

    • Dequeue (0, 1), increment area to 2.
    • Explore neighbors:
      • Right: (0, 2) -> Valid, add to queue, mark visited (grid[0][2] = 0).
      • Down: (1, 1) -> Valid, add to queue, mark visited (grid[1][1] = 0).
      • Left: (0, 0) -> Valid, but already visited.
      • Up: (-1, 1) -> Invalid (out of bounds).
    • Queue: [(0, 2), (1, 1)].

  6. Third Iteration of BFS:

    • Dequeue (0, 2), increment area to 3.
    • Explore neighbors:
      • Right: (0, 3) -> Valid, but contains 0.
      • Down: (1, 2) -> Valid, but contains 0.
      • Left: (0, 1) -> Valid, but already visited.
      • Up: (-1, 2) -> Invalid (out of bounds).
    • Queue: [(1, 1)].

  7. Fourth Iteration of BFS:

    • Dequeue (1, 1), increment area to 4.
    • Explore neighbors:
      • Right: (1, 2) -> Valid, but contains 0.
      • Down: (2, 1) -> Valid, but contains 0.
      • Left: (1, 0) -> Valid, but contains 0.
      • Up: (0, 1) -> Valid, but already visited.
    • Queue: [].

  8. End of BFS from (0, 0):

    • BFS returns area of 4.
    • maxArea is updated to 4.

  9. Continue Traversal:

    • Skip cells (0, 1) and (0, 2) as they are visited.
    • Cell (0, 3) contains 0, skip.
    • Cell (0, 4) contains 0, skip.

  10. Index (1, 0):

    • Cell (1, 0) contains 0, skip.

  11. Index (1, 1):

    • Cell (1, 1) already visited, skip.

  12. Index (1, 2):

    • Cell (1, 2) contains 0, skip.

  13. Index (1, 3):

    • Cell (1, 3) contains 0, skip.

  14. Index (1, 4):

    • Cell (1, 4) contains 1. Call bfs with (1, 4).

  15. BFS from (1, 4):

    • Initialize queue with (1, 4).
    • Mark (1, 4) as visited (grid[1][4] = 0).
    • Initialize area to 0.

  16. First Iteration of BFS:

    • Dequeue (1, 4), increment area to 1.
    • Explore neighbors:
      • Right: (1, 5) -> Invalid (out of bounds).
      • Down: (2, 4) -> Valid, but contains 0.
      • Left: (1, 3) -> Valid, but contains 0.
      • Up: (0, 4) -> Valid, but contains 0.
    • Queue: [].

  17. End of BFS from (1, 4):

    • BFS returns area of 1.
    • maxArea remains 4.

  18. Continue Traversal:

    • Cell (2, 0) contains 0, skip.
    • Cell (2, 1) contains 0, skip.
    • Cell (2, 2) contains 1. Call bfs with (2, 2).

  19. BFS from (2, 2):

    • Initialize queue with (2, 2).
    • Mark (2, 2) as visited (grid[2][2] = 0).
    • Initialize area to 0.

  20. First Iteration of BFS:

    • Dequeue (2, 2), increment area to 1.
    • Explore neighbors:
      • Right: (2, 3) -> Valid, add to queue, mark visited (grid[2][3] = 0).
      • Down: (3, 2) -> Valid, add to queue, mark visited (grid[3][2] = 0).
      • Left: (2, 1) -> Valid, but contains 0.
      • Up: (1, 2) -> Valid, but contains 0.
    • Queue: [(2, 3), (3, 2)].

  21. Second Iteration of BFS:

    • Dequeue (2, 3), increment area to 2.
    • Explore neighbors:
      • Right: (2, 4) -> Valid, but contains 0.
      • Down: (3, 3) -> Valid, but contains 0.
      • Left: (2, 2) -> Valid, but already visited.
      • Up: (1, 3) -> Valid, but contains 0.
    • Queue: [(3, 2)].

  22. Third Iteration of BFS:

    • Dequeue (3, 2), increment area to 3.
    • Explore neighbors:
      • Right: (3, 3) -> Valid, but contains 0.
      • Down: (4, 2) -> Valid, add to queue, mark visited (grid[4][2] = 0).
      • Left: (3, 1) -> Valid, add to queue, mark visited (grid[3][1] = 0).
      • Up: (2, 2) -> Valid, but already visited.
    • Queue: [(4, 2), (3, 1)].

  23. Fourth Iteration of BFS:

    • Dequeue (4, 2), increment area to 4.
    • Explore neighbors:
      • Right: (4, 3) -> Valid, but contains 0.
      • Down: (5, 2) -> Invalid (out of bounds).
      • Left: (4, 1) -> Valid, but contains 0.
      • Up: (3, 2) -> Valid, but already visited.
    • Queue: [(3, 1)].

  24. Fifth Iteration of BFS:

    • Dequeue (3, 1), increment area to 5.
    • Explore neighbors:
      • Right: (3, 2) -> Valid, but already visited.
      • Down: (4, 1) -> Valid, but contains 0.
      • Left: (3, 0) -> Valid, but contains 0.
      • Up: (2, 1) -> Valid, but contains 0.
    • Queue: [].

  25. End of BFS from (2, 2):

    • BFS returns area of 5.
    • maxArea is updated to 5.

  26. Continue Traversal:

    • Skip cells (2, 3), (2, 4), (3, 0), (3, 1), (3, 2), (3, 3), (3, 4), (4, 0), (4, 1), and (4, 2) as they are visited or contain 0.

  27. Return Result:

    • After traversing the entire grid, maxArea is 5.

Code

Python3
Python3
. . . .

Complexity Analysis

  • Time Complexity: O(N \times M)

    • Grid Traversal: The nested for-loops traverse each cell in the grid once. Therefore, this part of the algorithm has a time complexity of O(N \times M), where (N) is the number of rows and (M) is the number of columns in the grid.
    • BFS Traversal: For each land cell (1), the BFS traversal explores all connected land cells. Since each cell is processed at most once, the total time spent in BFS across all cells is O(N \times M).

Combining these, the total time complexity is O(N \times M).

  • Space Complexity:O(N \times M)

    • Visited Marking: The algorithm marks cells as visited in-place, so no additional space is required for a visited array.
    • Queue for BFS: In the worst case, the queue can contain O(min(N, M)) number of cells.

Therefore, the overall space complexity is O(N \times M) + O(min(N, M)), which is equal to O(N \times M).

Mark as Completed