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.

largestIsland.js

/**
 * @param {number[][]} grid
 * @return {number}
 */
var largestIsland = function(grid) {
    const n = grid.length;

    // Helper function to perform DFS and mark island cells with a unique island ID
    function dfs(x, y, islandId) {
        const stack = [[x, y]];
        let size = 0;

        while (stack.length) {
            const [cx, cy] = stack.pop();
            if (cx < 0 || cx >= n || cy < 0 || cy >= n || grid[cx][cy] !== 1) continue;
            grid[cx][cy] = islandId; // Mark the cell with the island ID
            size++;
            stack.push([cx - 1, cy], [cx + 1, cy], [cx, cy - 1], [cx, cy + 1]); // Explore 4-directionally
        }

        return size;
    }

    const islandSizes = {};
    let islandId = 2; // Start island IDs from 2 (0 and 1 are already used in grid)

    // Step 1: Identify and label all initial islands
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === 1) {
                const size = dfs(i, j, islandId);
                islandSizes[islandId] = size;
                islandId++;
            }
        }
    }

    // Step 2: Evaluate changing each 0 to 1
    let maxIslandSize = Math.max(...Object.values(islandSizes), 0);

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === 0) {
                let newSize = 1; // Changing the current 0 to 1
                const visitedIslands = new Set();

                // Check neighboring cells and calculate potential new island size
                for (const [dx, dy] of [[-1, 0], [1, 0], [0, -1], [0, 1]]) {
                    const nx = i + dx;
                    const ny = j + dy;

                    if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] > 1) {
                        const neighborIslandId = grid[nx][ny];
                        if (!visitedIslands.has(neighborIslandId)) {
                            visitedIslands.add(neighborIslandId);
                            newSize += islandSizes[neighborIslandId];
                        }
                    }
                }

                maxIslandSize = Math.max(maxIslandSize, newSize);
            }
        }
    }

    return maxIslandSize; 
};