Grokking the Coding Interview: Patterns for Coding Questions

0% completed

Solution: Biggest Island

On This Page

Problem Statement

Why this is an Island problem

Solution

Step-by-step Algorithm

Code (DFS)

An Alternate Approach (Using BFS)

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

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 =

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

Constraints:

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

Why this is an Island problem

What the question says	The signal it matches
"return the area of the biggest island"	the question asks about areas inside the grid
"a connected set of 1s"	the wording includes island

This is the measure a region variant: the traversal returns a size instead of nothing.

The closest alternative. There is none. This is Number of Islands with one change: the traversal reports how many cells it visited, and the caller keeps the largest report.

The change sounds small and it is the whole variant. A counting traversal returns nothing, because starting it is the event that matters. A measuring traversal returns a number, built by adding one for the current cell to whatever the four cells around it return. Most grid questions in this chapter are one of these two shapes.

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:

We first initialize biggestIslandArea to 0. This variable will keep track of the largest island's area we have encountered so far.
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.
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.
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.
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).
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.
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:

Biggest Island

Code (DFS)

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

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.

The lesson does not end here. Keep scrolling: An Alternate Approach (Using BFS) below solves the same question a different way, with its own code and its own complexity analysis.

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

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).
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.
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.
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 }
}

Initialization:
- maxArea is set to 0.
- rows is 5, cols is 5.
- directions is {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}.
Grid Traversal:
- Start at cell (0, 0), which contains 1. Call bfs with (0, 0).
BFS from (0, 0):
- Initialize queue with (0, 0).
- Mark (0, 0) as visited (grid[0][0] = 0).
- Initialize area to 0.
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)].
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)].
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)].
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: [].
End of BFS from (0, 0):
- BFS returns area of 4.
- maxArea is updated to 4.
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.
Index (1, 0):
- Cell (1, 0) contains 0, skip.
Index (1, 1):
- Cell (1, 1) already visited, skip.
Index (1, 2):
- Cell (1, 2) contains 0, skip.
Index (1, 3):
- Cell (1, 3) contains 0, skip.
Index (1, 4):
- Cell (1, 4) contains 1. Call bfs with (1, 4).
BFS from (1, 4):
- Initialize queue with (1, 4).
- Mark (1, 4) as visited (grid[1][4] = 0).
- Initialize area to 0.
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: [].
End of BFS from (1, 4):
- BFS returns area of 1.
- maxArea remains 4.
Continue Traversal:
- Cell (2, 0) contains 0, skip.
- Cell (2, 1) contains 0, skip.
- Cell (2, 2) contains 1. Call bfs with (2, 2).
BFS from (2, 2):
- Initialize queue with (2, 2).
- Mark (2, 2) as visited (grid[2][2] = 0).
- Initialize area to 0.
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)].
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)].
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)].
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)].
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: [].
End of BFS from (2, 2):
- BFS returns area of 5.
- maxArea is updated to 5.
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.
Return Result:
- After traversing the entire grid, maxArea is 5.

Code

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(min(N, M))$
- Visited Marking: The algorithm marks cells as visited in place, by writing 0 over each land cell it has counted, so no separate visited array is needed and this step costs nothing extra.
- Queue for BFS: In the worst case, the queue can contain $O(min(N, M))$ cells. A breadth first search on a grid spreads out as a diagonal band, and a diagonal band cannot be longer than the shorter side of the grid.

Since the marking costs nothing extra, the queue is the only additional space the algorithm uses, so the overall space complexity is $O(min(N, M))$ .

This is the one place where BFS beats the DFS version above. DFS uses the call stack instead of a queue, and that stack can reach $M \times N$ frames when the whole grid is a single island, so its space complexity is $O(M \times N)$ . If the grid can be large, prefer the BFS version.

Mark as Completed

Tobby Lie

· 2 years ago

The BFS solution provided seems unnecessarily complicated, this is what I have in Python that has a space complexity of O(min(m, n)) rather than the O(m * n) described in the solution...

from collections import deque

class Solution:
  def maxAreaOfIsland(self, matrix):
    biggestIslandArea = 0
    rows = len(matrix)
    cols = len(matrix[0])
    for i in range(rows):
      for j in range(cols):
        if matrix[i][j] == 1:
          biggestIslandArea = max(biggestIslandArea, self.visit_land_bfs(matrix, i, j))
    return biggestIslandArea

  def visit_land_bfs(self, matrix, x, y):
    neighbors = deque([(x, y)])
    area = 0

    while neighbors:
      x, y = neighbors.popleft()

      if x < 0 or x >= len(matrix) or y < 0 or y >= len(matrix[0]):
        continue
      if mat

Show 1 reply

Thai Minh

· 3 years ago

from collections import deque
class Solution:
  def maxAreaOfIsland(self, matrix):
    biggestIslandArea = 0
    # TODO: Write your code here
    # loop through matrix to see if we can find an island
    # call visitNeighborIsland to calculate the size of island
    for row in range(len(matrix)):
      for col in range(len(matrix[0])):
        if matrix[row][col] == 1:
          currSizeIsland = self.visitNeighborIslandBFS(row, col, matrix)
          biggestIslandArea = max(biggestIslandArea, currSizeIsland)
    return biggestIslandArea
  
  def visitNeighborIslandDFS(self, row, col, matrix, currSize):
    if row < 0 or row >= len(matrix) or col < 0 or col >= len(matrix[0]):
      return 0
    if matrix[row][col] == 0:
      return 0
    currSize = 1
    matrix[row][col] = 0

venkat narsim

· 3 years ago

class Solution {
  maxAreaOfIsland(matrix) {
    let biggestIslandArea = 0;
    let islandCounter = [];
    let row = matrix.length;
    let col = matrix[0].length;
    let visitedMatrix = Array(row).fill(false).map(() => Array(col).fill(false));
    for(let i=0; i<row; i++) {
        for(let j=0; j<col; j++) {
            if(matrix[i][j] === 1 && visitedMatrix[i][j] === false) {
                biggestIslandArea = visitedMatrixFiller(matrix, visitedMatrix, biggestIslandArea, i,j);
                islandCounter.push(biggestIslandArea);
                biggestIslandArea = 0;
            }
        }
    }
    console.log(islandCounter); --> This produces [4,1,5]
    return Math.max(islandCounter); --> This produces null
  }
}

function visitedMatrixFiller(matrix, visitedMatrix,

krishnakeshav.pes

· 3 years ago

Show 1 reply

Alan Ross

· 4 years ago

Show 2 replies

Reading Progress

Vote for new content

On This Page

Problem Statement

Why this is an Island problem

Solution

Step-by-step Algorithm

Code (DFS)

An Alternate Approach (Using BFS)

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis