827. Making A Large Island

[mah-shamim]

Topics: Array, Depth-First Search, Breadth-First Search, Union Find, Matrix

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.length
• n == grid[i].length
• 1 <= n <= 500
• grid[i][j] is either 0 or 1.

[mah-shamim]

To solve the problem of making a large island by changing at most one 0 to 1 in a binary matrix, we can follow these steps:

1. Identify Islands: First, we need to identify all the existing islands in the grid and assign a unique identifier to each island. We can use Depth-First Search (DFS) or Breadth-First Search (BFS) to traverse the grid and mark each cell of an island with a unique ID.

2. Calculate Island Sizes: As we identify each island, we calculate its size and store it in a dictionary or array where the key is the island ID and the value is the size of the island.

3. Find the Best 0 to Flip: For each 0 in the grid, we check its neighboring cells to see if they belong to different islands. If they do, we calculate the potential size of the new island that would be formed by flipping this 0 to 1. We keep track of the maximum size found.

4. Return the Result: Finally, we return the maximum size found. If there are no 0s in the grid, we return the size of the largest island.

Let's implement this solution in PHP: 827. Making A Large Island

<?php
/**
 * @param Integer[][] $grid
 * @return Integer
 */
function largestIsland($grid) {
    $n = count($grid);
    $islandId = 2; // Start assigning island IDs from 2
    $islandSizes = array(); // To store the size of each island

    // Step 1: Identify islands and calculate their sizes
    for ($i = 0; $i < $n; $i++) {
        for ($j = 0; $j < $n; $j++) {
            if ($grid[$i][$j] == 1) {
                $size = 0;
                $this->dfs($grid, $i, $j, $islandId, $size);
                $islandSizes[$islandId] = $size;
                $islandId++;
            }
        }
    }

    // Step 2: Find the best 0 to flip
    $maxSize = 0;
    foreach ($islandSizes as $size) {
        $maxSize = max($maxSize, $size);
    }

    for ($i = 0; $i < $n; $i++) {
        for ($j = 0; $j < $n; $j++) {
            if ($grid[$i][$j] == 0) {
                $neighbors = array();
                $potentialSize = 1;

                // Check all four directions
                if ($i > 0 && $grid[$i-1][$j] > 1) {
                    $neighbors[$grid[$i-1][$j]] = true;
                }
                if ($i < $n-1 && $grid[$i+1][$j] > 1) {
                    $neighbors[$grid[$i+1][$j]] = true;
                }
                if ($j > 0 && $grid[$i][$j-1] > 1) {
                    $neighbors[$grid[$i][$j-1]] = true;
                }
                if ($j < $n-1 && $grid[$i][$j+1] > 1) {
                    $neighbors[$grid[$i][$j+1]] = true;
                }

                foreach ($neighbors as $id => $val) {
                    $potentialSize += $islandSizes[$id];
                }

                $maxSize = max($maxSize, $potentialSize);
            }
        }
    }

    return $maxSize;
}

/**
 * Helper function to perform DFS and calculate component size
 *
 * @param $grid
 * @param $i
 * @param $j
 * @param $islandId
 * @param $size
 * @return void
 */
function dfs(&$grid, $i, $j, $islandId, &$size) {
    $n = count($grid);
    if ($i < 0 || $i >= $n || $j < 0 || $j >= $n || $grid[$i][$j] != 1) {
        return;
    }

    $grid[$i][$j] = $islandId;
    $size++;

    // Explore all four directions
    $this->dfs($grid, $i-1, $j, $islandId, $size);
    $this->dfs($grid, $i+1, $j, $islandId, $size);
    $this->dfs($grid, $i, $j-1, $islandId, $size);
    $this->dfs($grid, $i, $j+1, $islandId, $size);
}

// Example usage
$grid1 = [[1, 0], [0, 1]];
$grid2 = [[1, 1], [1, 0]];
$grid3 = [[1, 1], [1, 1]];

echo largestIsland($grid1) . "\n"; // Output: 3
echo largestIsland($grid2) . "\n"; // Output: 4
echo largestIsland($grid3) . "\n"; // Output: 4
?>

Explanation:

1. DFS Traversal:
   A DFS is used to traverse each island (group of connected 1s) and assign it a unique ID starting from 2. The size of the island is recorded in the componentSize array.

2. Flipping a 0:
   For every cell with a 0, the code checks its neighbors and calculates the potential size of the island formed if the 0 were flipped to 1. It ensures that each neighboring island is only counted once using a uniqueComponents array.

3. Max Island Size:
   The maximum size is updated as we calculate the sizes for all possible flips of 0.

4. Edge Cases:

   • If the grid is entirely 1s, the maximum island size is the total grid size.
   • If there's only one island, flipping a 0 connects the largest number of 1s.

This solution efficiently handles the problem constraints and provides the correct result.

[kovatz]

Thanks for solving the problem of "Making A Large Island"

[mah-shamim]

Thanks