Making A Large Island
Problem Description
You are given an n x n binary matrix grid. You are allowed to change at most one 0 to be 1.
Return the size of the largest island in grid after applying this operation.
An island is a 4-directionally connected group of 1s.
Example 1:
Input: grid = [[1,0],[0,1]]
Output: 3
Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3.
Example 2:
Input: grid = [[1,1],[1,0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.
Example 3:
Input: grid = [[1,1],[1,1]]
Output: 4
Explanation: Can't change any 0 to 1, only one island with area = 4.
Constraints:
n == grid.lengthn == grid[i].length1 <= n <= 500grid[i][j]is either0or1.
Solve it on LeetCode
Approaches
1. Brute Force Approach
Intuition:
In this initial approach, the goal is to change each 0 in the grid to 1 one by one and calculate the size of the island it can form. For each conversion, we calculate the potential size of the island and keep track of the maximum size encountered. The key idea is to perform a depth-first search (DFS) to calculate the size of each connected component (island).
Steps:
- For each cell in the grid that contains a
0, temporarily change it to a1. - Use DFS to calculate the size of the island this change creates.
- Restore the cell back to
0and continue to the next0. - Return the maximum island size found.
Code:
- Time Complexity: O(n^4), where n is the size of the grid. For each
0in the grid, a complete DFS traversal happens. - Space Complexity: O(n^2), due to the visited matrix.
2. Optimized Approach with Connected Components
Intuition:
To optimize, pre-calculate the sizes of all connected components (islands) and then analyze the potential contributions of each 0 within the grid. We use different numeric IDs for different islands and store the size corresponding to each ID. This approach reduces unnecessary recalculations.
Steps:
- Assign unique IDs to each connected component using DFS and calculate their sizes.
- Store these sizes in a map with the ID as the key.
- For each
0, check its 4 neighboring cells and sum the sizes of distinct islands formed by adjacent1s. - The maximum size achieved by flipping a
0is stored as the result.
Code:
- Time Complexity: O(n^2), where n is the size of the grid. Each cell is part of a recursive DFS once.
- Space Complexity: O(n^2), due to storage in the size map and for visited routes.