LeetCode/cs/making-a-large-island.cs

using Coord = (int x, int y);

public class Solution {
    private static readonly List<Coord> DIRS = [(0, 1), (0, -1), (1, 0), (-1, 0)];

    private static bool InBounds(int[][] grid, Coord pos)
        => pos.y >= 0 && pos.y < grid.Length && pos.x >= 0 && pos.x < grid[pos.y].Length;

    private static Coord Add(Coord pos, Coord d) => (pos.x + d.x, pos.y + d.y);

    private static IEnumerable<Coord> Coords(int[][] grid) =>
        Enumerable
        .Range(0, grid.Length)
        .SelectMany(
            y => Enumerable.Range(0, grid[y].Length).Select(x => (x, y))
        );

    private static int ExploreIsland(int[][] grid, int island, Coord pos) {
        if (!InBounds(grid, pos) || grid[pos.y][pos.x] != 1) {
            return 0;
        }

        grid[pos.y][pos.x] = island;
        return 1 + DIRS.Sum(
            d => ExploreIsland(grid, island, Add(pos, d))
        );
    }

    public int LargestIsland(int[][] grid) {
        var islands = new Dictionary<int, int>();
        var islandId = 2;

        // Discover islands
        foreach (var pos in Coords(grid).Where(pos => grid[pos.y][pos.x] == 1)) {
            islands[islandId] = ExploreIsland(grid, islandId, pos);
            ++islandId;
        }

        switch (islands.Count) {
            case 0:
                // can only toggle one cell
                return 1;
            case 1:
                --islandId;
                if (islands[islandId] < grid.Length * grid[0].Length) {
                    // doesn't cover whole grid, can extend by one cell
                    ++islands[islandId];
                }

                return islands[islandId];
        }

        return Coords(grid)
            .Where(pos => grid[pos.y][pos.x] == 0)
            .Max(pos => 1 + DIRS
                .Select(d => Add(pos, d))
                .Where(pos => InBounds(grid, pos) && grid[pos.y][pos.x] > 1)
                .Select(pos => grid[pos.y][pos.x])
                .Distinct()
                .Sum(id => islands[id])
            );
    }
}