Painting a large Island

83.Making a Large Island

Graph

Depth-First Search

Problem Statement:

Given an n x n binary grid, you can change at most one 0 to a 1. Return the size of the largest island in the resulting grid. An island is a group of 1's connected vertically or horizontally. You may assume there is at least one 1 in the grid.

Algorithm:

1. Assign a unique color to each island using DFS to "paint" the grid and calculate the size of each island.
2. Store the mapping of colors to island sizes in a hash map.
3. Iterate through each cell in the grid:
• If the cell is 0, calculate the size of the island that would form if this cell were changed to 1.
• Use a set to track unique adjacent island colors and sum their sizes from the hash map.
• Update the result with the maximum size found.
4. If no cell is changed, return the size of the largest island already present.

Complexity:

Time: O(n²) | Space: O(n²)

Java Implementation:

public int largestIsland(int[][] grid) {
    Map map = new HashMap<>(); // Map to store island color and size
    map.put(0, 0); // Size of water (0) is 0
    int n = grid.length;
    int colorIndex = 2; // Start painting islands with color 2
    
    // Paint each island with a unique color and calculate its size
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                int size = paint(grid, i, j, colorIndex);
                map.put(colorIndex, size);
                colorIndex++;
            }
        }
    }

    int res = map.getOrDefault(2, 0); // Initialize result with size of the largest painted island

    // Try turning each 0 into a 1 to see the largest island that can be formed
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 0) {
                Set set = new HashSet<>(); // Store unique adjacent island colors
                set.add(i > 0 ? grid[i - 1][j] : 0);
                set.add(i < n - 1 ? grid[i + 1][j] : 0);
                set.add(j > 0 ? grid[i][j - 1] : 0);
                set.add(j < n - 1 ? grid[i][j + 1] : 0);

                int newSize = 1; // Count the current cell
                for (int color : set) newSize += map.get(color); // Add sizes of adjacent islands
                res = Math.max(res, newSize);
            }
        }
    }
    return res;
}

// Helper function to paint an island and calculate its size
private int paint(int[][] grid, int i, int j, int color) {
    if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] != 1) return 0;
    grid[i][j] = color;
    return 1 + paint(grid, i + 1, j, color) + paint(grid, i - 1, j, color) + paint(grid, i, j + 1, color) + paint(grid, i, j - 1, color);
}

Python Implementation:

def largestIsland(grid):
    n = len(grid)
    color_index = 2
    size_map = {0: 0}  # Map to store island color and size

    def paint(x, y, color):
        if x < 0 or y < 0 or x >= n or y >= n or grid[x][y] != 1:
            return 0
        grid[x][y] = color
        return 1 + paint(x + 1, y, color) + paint(x - 1, y, color) + paint(x, y + 1, color) + paint(x, y - 1, color)

    # Paint islands with unique colors and calculate sizes
    for i in range(n):
        for j in range(n):
            if grid[i][j] == 1:
                size_map[color_index] = paint(i, j, color_index)
                color_index += 1

    res = max(size_map.values())  # Start with the largest existing island size

    # Try turning each 0 into 1 and calculate the potential island size
    for i in range(n):
        for j in range(n):
            if grid[i][j] == 0:
                seen_colors = {grid[x][y] for x, y in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)] if 0 <= x < n and 0 <= y < n}
                new_size = 1 + sum(size_map[color] for color in seen_colors)
                res = max(res, new_size)

    return res

C++ Implementation:

#include 
#include 
#include 
#include 
using namespace std;

class Solution {
public:
    int largestIsland(vector>& grid) {
        int n = grid.size();
        unordered_map size_map = {{0, 0}};
        int color_index = 2;

        auto paint = [&](int x, int y, int color) -> int {
            if (x < 0 || y < 0 || x >= n || y >= n || grid[x][y] != 1) return 0;
            grid[x][y] = color;
            return 1 + paint(x + 1, y, color) + paint(x - 1, y, color) + paint(x, y + 1, color) + paint(x, y - 1, color);
        };

        // Paint islands with unique colors and calculate sizes
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    size_map[color_index] = paint(i, j, color_index);
                    color_index++;
                }
            }
        }

        int res = max_element(size_map.begin(), size_map.end(),
            [](const auto& a, const auto& b) { return a.second < b.second; })->second;

        // Try turning each 0 into 1 and calculate the potential island size
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0) {
                    unordered_set seen_colors = {grid[x][y] for (x, y) in {(i-1, j), (i+1, j), (i, j-1), (i, j+1)}};
                    int new_size = 1 + accumulate(seen_colors.begin(), seen_colors.end(), 0,
                        [&](int acc, int color) { return acc + size_map[color]; });
                    res = max(res, new_size);
                }
            }
        }

        return res;
    }
};