0% completed
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'.
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.
Stepbystep 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:
Code (DFS)
Here is what our DFS algorithm will look like. We will update the input matrix to mark nodes visited.
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 BreadthFirst 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.
StepbyStep 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).
 Define a method

Grid Traversal:
 Loop through each cell in the grid using nested forloops:
 For each cell at position
(i, j)
, if the cell contains1
(indicating land), call the BFS methodbfs
and updatemaxArea
with the maximum value betweenmaxArea
and the result ofbfs
.
 For each cell at position
 Loop through each cell in the grid using nested forloops:

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 thearea
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 to0
.
 Dequeue a cell
 Return the computed
area
.
 Define a method

Return Result:
 After traversing the entire grid, return
maxArea
.
 After traversing the entire grid, return
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 contains1
. Callbfs
with(0, 0)
.
 Start at cell

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

First Iteration of BFS:
 Dequeue
(0, 0)
, incrementarea
to 1.  Explore neighbors:
 Right:
(0, 1)
> Valid, add to queue, mark visited (grid[0][1] = 0
).  Down:
(1, 0)
> Valid, but contains0
.  Left:
(0, 1)
> Invalid (out of bounds).  Up:
(1, 0)
> Invalid (out of bounds).
 Right:
 Queue:
[(0, 1)]
.
 Dequeue

Second Iteration of BFS:
 Dequeue
(0, 1)
, incrementarea
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).
 Right:
 Queue:
[(0, 2), (1, 1)]
.
 Dequeue

Third Iteration of BFS:
 Dequeue
(0, 2)
, incrementarea
to 3.  Explore neighbors:
 Right:
(0, 3)
> Valid, but contains0
.  Down:
(1, 2)
> Valid, but contains0
.  Left:
(0, 1)
> Valid, but already visited.  Up:
(1, 2)
> Invalid (out of bounds).
 Right:
 Queue:
[(1, 1)]
.
 Dequeue

Fourth Iteration of BFS:
 Dequeue
(1, 1)
, incrementarea
to 4.  Explore neighbors:
 Right:
(1, 2)
> Valid, but contains0
.  Down:
(2, 1)
> Valid, but contains0
.  Left:
(1, 0)
> Valid, but contains0
.  Up:
(0, 1)
> Valid, but already visited.
 Right:
 Queue:
[]
.
 Dequeue

End of BFS from (0, 0):
 BFS returns
area
of 4. maxArea
is updated to 4.
 BFS returns

Continue Traversal:
 Skip cells
(0, 1)
and(0, 2)
as they are visited.  Cell
(0, 3)
contains0
, skip.  Cell
(0, 4)
contains0
, skip.
 Skip cells

Index (1, 0):
 Cell
(1, 0)
contains0
, skip.
 Cell

Index (1, 1):
 Cell
(1, 1)
already visited, skip.
 Cell

Index (1, 2):
 Cell
(1, 2)
contains0
, skip.
 Cell

Index (1, 3):
 Cell
(1, 3)
contains0
, skip.
 Cell

Index (1, 4):
 Cell
(1, 4)
contains1
. Callbfs
with(1, 4)
.
 Cell

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

First Iteration of BFS:
 Dequeue
(1, 4)
, incrementarea
to 1.  Explore neighbors:
 Right:
(1, 5)
> Invalid (out of bounds).  Down:
(2, 4)
> Valid, but contains0
.  Left:
(1, 3)
> Valid, but contains0
.  Up:
(0, 4)
> Valid, but contains0
.
 Right:
 Queue:
[]
.
 Dequeue

End of BFS from (1, 4):
 BFS returns
area
of 1. maxArea
remains 4.
 BFS returns

Continue Traversal:
 Cell
(2, 0)
contains0
, skip.  Cell
(2, 1)
contains0
, skip.  Cell
(2, 2)
contains1
. Callbfs
with(2, 2)
.
 Cell

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

First Iteration of BFS:
 Dequeue
(2, 2)
, incrementarea
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 contains0
.  Up:
(1, 2)
> Valid, but contains0
.
 Right:
 Queue:
[(2, 3), (3, 2)]
.
 Dequeue

Second Iteration of BFS:
 Dequeue
(2, 3)
, incrementarea
to 2.  Explore neighbors:
 Right:
(2, 4)
> Valid, but contains0
.  Down:
(3, 3)
> Valid, but contains0
.  Left:
(2, 2)
> Valid, but already visited.  Up:
(1, 3)
> Valid, but contains0
.
 Right:
 Queue:
[(3, 2)]
.
 Dequeue

Third Iteration of BFS:
 Dequeue
(3, 2)
, incrementarea
to 3.  Explore neighbors:
 Right:
(3, 3)
> Valid, but contains0
.  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.
 Right:
 Queue:
[(4, 2), (3, 1)]
.
 Dequeue

Fourth Iteration of BFS:
 Dequeue
(4, 2)
, incrementarea
to 4.  Explore neighbors:
 Right:
(4, 3)
> Valid, but contains0
.  Down:
(5, 2)
> Invalid (out of bounds).  Left:
(4, 1)
> Valid, but contains0
.  Up:
(3, 2)
> Valid, but already visited.
 Right:
 Queue:
[(3, 1)]
.
 Dequeue

Fifth Iteration of BFS:
 Dequeue
(3, 1)
, incrementarea
to 5.  Explore neighbors:
 Right:
(3, 2)
> Valid, but already visited.  Down:
(4, 1)
> Valid, but contains0
.  Left:
(3, 0)
> Valid, but contains0
.  Up:
(2, 1)
> Valid, but contains0
.
 Right:
 Queue:
[]
.
 Dequeue

End of BFS from (2, 2):
 BFS returns
area
of 5. maxArea
is updated to 5.
 BFS returns

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 contain0
.
 Skip cells

Return Result:
 After traversing the entire grid,
maxArea
is5
.
 After traversing the entire grid,
Code
Complexity Analysis

Time Complexity: O(N \times M)
 Grid Traversal: The nested forloops 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 inplace, 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).