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 and seen.


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 depth-first 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.