 ✅ Making A Large Island | JS🔥 | beats 99%🚀 | 🚀highly optimised & easy to understand ✅
Intuition
Here's an optimized JavaScript solution using DFS (Depth-First Search) and Union-Find techniques to efficiently solve the problem for large grids up t
# Intuition
- Here's an optimized JavaScript solution using DFS (Depth-First Search) and Union-Find techniques to efficiently solve the problem for large grids up to 500×500.
# Approach
> **Optimized Approach**
- Label Islands: Use DFS to label each island with a unique index and calculate its area.
- Store Island Sizes: Maintain a Map that stores the area of each island by its label.
- Find Best 0 to Flip: Iterate through all 0s and check the sum of unique adjacent island areas.
- Return the Maximum Possible Island Size.
> **Explanation**
- **Step 1:** Label Islands and Store Their Sizes
- Each island is given a unique label (2, 3, ...).
- A DFS (or BFS) traversal is used to calculate its area and store it in a Map.
- **Step 2:** Check All 0s to Find the Best Flip
- For each 0, check adjacent unique island labels.
- Sum up their sizes to get the maximum possible island size.
> **Edge Cases Considered**
- If the grid is already full of 1s, return the existing largest island size.
- If there's only one cell (n=1), handle separately.
# Complexity
- **DFS Traversal:** 𝑂(𝑛2), as we visit each cell once.
- **Processing 0s:** 𝑂(𝑛2), since we check at most 4 neighbors for each cell.
- **Overall Complexity:** 𝑂(𝑛2), making it efficient for n≤500.

# Code
```javascript []
/**
 * @param {number[][]} grid
 * @return {number}
 */
var largestIsland = function (grid) {
    const n = grid.length;
    const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    let islandId = 2; // Start from 2 to differentiate from 1s
    let islandSizes = new Map();

    // Function to perform DFS and mark the island
    const dfs = (r, c, id) => {
        let stack = [[r, c]];
        let size = 0;
        grid[r][c] = id; // Mark as visited with island ID

        while (stack.length) {
            let [x, y] = stack.pop();
            size++;
            for (let [dx, dy] of directions) {
                let nx = x + dx, ny = y + dy;
                if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] === 1) {
                    grid[nx][ny] = id;
                    stack.push([nx, ny]);
                }
            }
        }
        return size;
    };

    // Step 1: Label each island and store its area
    for (let r = 0; r < n; r++) {
        for (let c = 0; c < n; c++) {
            if (grid[r][c] === 1) {
                islandSizes.set(islandId, dfs(r, c, islandId));
                islandId++;
            }
        }
    }

    let maxIsland = Math.max(...islandSizes.values(), 0); // Default to 0 if no islands

    // Step 2: Check each 0 and compute max possible island size
    for (let r = 0; r < n; r++) {
        for (let c = 0; c < n; c++) {
            if (grid[r][c] === 0) {
                let seen = new Set();
                let newSize = 1;

                for (let [dx, dy] of directions) {
                    let nx = r + dx, ny = c + dy;
                    if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] > 1) {
                        let id = grid[nx][ny];
                        if (!seen.has(id)) {
                            seen.add(id);
                            newSize += islandSizes.get(id);
                        }
                    }
                }
                maxIsland = Math.max(maxIsland, newSize);
            }
        }
    }

    return maxIsland;
};
```


![DALL·E 2025-01-21 10.20.30 - A realistic, soft-toned image of a kind and humble person, sitting at a desk with a gentle smile, holding a sign that says_ 'Please upvote if this hel.webp](https://assets.leetcode.com/users/images/21f42ea0-660f-4740-b0d4-a2b07c993daa_1738294492.4781811.webp)

['JavaScript']