827. Making A Large Island - Detailed Explanation

Problem Statement

Description:
You are given an ( n \times n ) binary matrix grid where:

• grid[i][j] = 1 represents land.
• grid[i][j] = 0 represents water.

An island is defined as a group of connected 1's (land) connected 4-directionally (up, down, left, right). You are allowed to change at most one 0 to a 1, with the goal of maximizing the size (number of cells) of the island. Return the size of the largest island possible after performing at most one conversion.

Examples:

1. Example 1:

   • Input:

     grid = [
       [1, 0],
       [0, 1]
     ]
     

   • Output: 3
   • Explanation:
     Initially, there are two islands each of size 1. If you flip one of the 0's to a 1 (for example, at position (0,1) or (1,0)), the two islands will connect to form an island of size 3.

2. Example 2:

   • Input:

     grid = [
       [1, 1],
       [1, 0]
     ]
     

   • Output: 4
   • Explanation:
     The island of land has size 3. By flipping the bottom-right 0 to 1, you obtain a single island covering all 4 cells.

3. Example 3:

   • Input:

     grid = [
       [1, 1],
       [1, 1]
     ]
     

   • Output: 4
   • Explanation:
     The grid is already all land, so the maximum island size is (4) (which is ( n \times n )). No flip is needed.

Constraints:

• ( 1 \leq n \leq 500 )
• grid[i][j] is either 0 or 1.

Hints

• Hint 1:
  Consider first finding and labeling all islands. Use Depth-First Search (DFS) or Breadth-First Search (BFS) to assign a unique island ID to each connected component (island) and compute its area (size).

• Hint 2:
  For every water cell (a 0), look at its 4 neighbors and collect the unique island IDs. The potential island size when flipping that water cell will be the sum of the sizes of these distinct neighboring islands plus 1 (for the flipped cell). Keep track of the maximum such sum.

Approaches

Approach 1: DFS with Island Labeling and Area Mapping

Step-by-Step Walkthrough

1. Labeling Islands:

   • Traverse the grid and perform a DFS (or BFS) from every unvisited land cell (cell with 1).
   • For each island, assign a unique ID (start from 2 or any number that does not conflict with 0 and 1).
   • While exploring an island, calculate its area (number of cells) and store the result in a map (e.g., islandArea where key is island ID and value is area).

2. Handling the Edge Case:

   • If the entire grid is all 1's, simply return ( n \times n ) because no flip is needed.

3. Evaluating Water Cells:

   • For each cell that is 0, check its 4 neighbors.
   • Use a set to collect unique neighboring island IDs (to avoid counting the same island twice).
   • Compute the potential area if you flipped that cell (sum the areas of all unique islands plus 1 for the cell itself).
   • Track the maximum island size seen.

4. Return the Answer:

   • The answer is the maximum island size found either by flipping one 0 or the largest island found in the original grid.

Pseudocode

function largestIsland(grid):
    n = grid.length
    islandArea = {}  // Maps island id to its area
    islandId = 2

    // DFS to mark islands and count area.
    function dfs(i, j, islandId):
        if i or j out of bounds or grid[i][j] != 1: return 0
        grid[i][j] = islandId
        area = 1
        for each direction (up, down, left, right):
            area += dfs(new_i, new_j, islandId)
        return area

    // Label islands and compute their areas.
    for i from 0 to n-1:
        for j from 0 to n-1:
            if grid[i][j] == 1:
                area = dfs(i, j, islandId)
                islandArea[islandId] = area
                islandId += 1

    maxArea = max(islandArea.values()) if islandArea is not empty else 0

    // Check every water cell.
    for i from 0 to n-1:
        for j from 0 to n-1:
            if grid[i][j] == 0:
                seen = empty set
                areaWithFlip = 1  // For the flipped cell.
                for each neighbor (i + di, j + dj) in up, down, left, right:
                    if neighbor in bounds and grid[neighbor] > 1:
                        islandId = grid[neighbor]
                        if islandId not in seen:
                            add islandId to seen
                            areaWithFlip += islandArea[islandId]
                maxArea = max(maxArea, areaWithFlip)

    return maxArea

Approach 2: Union-Find (Alternative)

While the DFS approach is more common and intuitive here, another possibility is to use a union-find data structure to merge connected cells. However, this approach is more complex to implement and is less common than DFS for grid problems.

Code Examples

Python Code