Approach #1: (Naive) Depth First Search [Time Limit Exceeded]
Intuition
For each 0
in the grid, let's temporarily change it to a 1
, then count the size of the group from that square.
Algorithm
For each 0
, change it to a 1
, then do a depth first search to find the size of that component. The answer is the maximum size component found.
Of course, if there is no 0
in the grid, then the answer is the size of the whole grid.
Complexity Analysis

Time Complexity: , where is the length and width of the
grid
. 
Space Complexity: , the additional space used in the depth first search by
stack
andseen
.
Approach #2: Component Sizes [Accepted]
Intuition
As in the previous solution, we check every 0
. However, we also store the size of each group, so that we do not have to use depthfirst search to repeatedly calculate the same size.
However, this idea fails when the 0
touches the same group. For example, consider grid = [[0,1],[1,1]]
. The answer is 4
, not 1 + 3 + 3
, since the right neighbor and the bottom neighbor of the 0
belong to the same group.
We can remedy this problem by keeping track of a group id (or index), that is unique for each group. Then, we'll only add areas of neighboring groups with different ids.
Algorithm
For each group, fill it with value index
and remember it's size as area[index] = dfs(...)
.
Then for each 0
, look at the neighboring group ids seen
and add the area of those groups, plus 1 for the 0
we are toggling. This gives us a candidate answer, and we take the maximum.
To solve the issue of having potentially no 0
, we take the maximum of the previously calculated areas.
Complexity Analysis

Time Complexity: , where is the length and width of the
grid
. 
Space Complexity: , the additional space used in the depth first search by
area
.
Analysis written by: @awice. Idea for Solution #2 by @lee215.