LeetCode 827 Making A Large Island

/**
 * LeetCode 827: Making A Large Island
 * 
 * Problem:
 * You are given an n x n binary matrix grid. A cell is considered a land cell if its value is 1,
 * and a water cell if its value is 0. You can change at most one water cell's value to 1.
 * Return the size of the largest island in grid after applying this operation.
 * An island is a 4-directionally connected group of 1s.
 * 
 * Approach:
 * 1. Label each island with a unique ID (starting from 2) and store their sizes
 * 2. For each water cell (0), check if converting it to land would connect any islands
 * 3. Calculate the maximum possible island size by combining adjacent islands
 * 
 * Time Complexity: O(N²), where N is the grid dimension
 * - Labeling islands: O(N²) to visit each cell once
 * - Finding largest possible island: O(N²) to check each water cell
 * 
 * Space Complexity: O(N²)
 * - islandSizes map: O(N²) in worst case where each cell is a separate island
 * - Recursion stack: O(N²) in worst case for DFS
 */

import java.util.*;

class Solution {
    // Directions array for 4-directional movement (right, left, down, up)
    private static final int[][] DIRECTIONS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    /**
     * Main method to find the largest possible island after changing at most one water cell
     * @param grid The input binary matrix
     * @return Size of the largest possible island
     */
    public int largestIsland(int[][] grid) {
        if (grid == null || grid.length == 0) return 0;

        int n = grid.length;
        Map<Integer, Integer> islandSizes = new HashMap<>();
        int maxIslandSize = 0;
        int islandId = 2; // Start from 2 as grid contains 0s and 1s

        // Step 1: Label islands and calculate their sizes
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    // For each unvisited land cell, perform DFS to label the island
                    int size = labelIsland(grid, i, j, islandId);
                    islandSizes.put(islandId, size);
                    maxIslandSize = Math.max(maxIslandSize, size);
                    islandId++;
                }
            }
        }

        // Handle edge cases
        if (maxIslandSize == 0) return 1; // Grid is all water
        if (maxIslandSize == n * n) return maxIslandSize; // Grid is all land

        // Step 2: Try to connect islands by changing water cells
        return findLargestPossibleIsland(grid, islandSizes, maxIslandSize);
    }

    /**
     * Labels all connected land cells with the given islandId using DFS
     * @return Size of the labeled island
     */
    private int labelIsland(int[][] grid, int row, int col, int islandId) {
        // Base case: out of bounds or not a land cell
        if (!isValid(row, col, grid.length) || grid[row][col] != 1) {
            return 0;
        }

        // Mark current cell as visited by labeling it
        grid[row][col] = islandId;
        int size = 1;

        // Recursively visit all adjacent land cells
        for (int[] dir : DIRECTIONS) {
            size += labelIsland(grid, row + dir[0], col + dir[1], islandId);
        }

        return size;
    }

    /**
     * Finds the largest possible island by trying to connect existing islands
     * @return Maximum possible island size
     */
    private int findLargestPossibleIsland(int[][] grid, Map<Integer, Integer> islandSizes, int currentMax) {
        int n = grid.length;
        int maxSize = currentMax;

        // Try each water cell
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    // Calculate size of island that would be formed by connecting neighbors
                    maxSize = Math.max(maxSize, calculateCombinedSize(grid, i, j, islandSizes));
                }
            }
        }

        return maxSize;
    }

    /**
     * Calculates the size of island that would be formed by changing cell (row,col) to land
     * @return Combined size of all unique neighboring islands plus 1
     */
    private int calculateCombinedSize(int[][] grid, int row, int col, Map<Integer, Integer> islandSizes) {
        Set<Integer> neighborIds = new HashSet<>();
        int totalSize = 1; // Include the current cell

        // Check all neighboring cells
        for (int[] dir : DIRECTIONS) {
            int newRow = row + dir[0];
            int newCol = col + dir[1];

            if (isValid(newRow, newCol, grid.length)) {
                int neighborId = grid[newRow][newCol];
                // Only add size if this is a new island (not water and not already counted)
                if (neighborId > 1 && neighborIds.add(neighborId)) {
                    totalSize += islandSizes.get(neighborId);
                }
            }
        }

        return totalSize;
    }

    /**
     * Checks if given coordinates are within grid boundaries
     */
    private boolean isValid(int row, int col, int n) {
        return row >= 0 && row < n && col >= 0 && col < n;
    }
}

class MakingLargeIslandTest {
    public static void main(String[] args) {
        Solution solution = new Solution();

        // Test Case 1: Basic case with opportunity to connect islands
        int[][] grid1 = {
            {1, 0, 1},
            {0, 0, 0},
            {1, 0, 1}
        };
        assert solution.largestIsland(grid1) == 5; // Converting center cell connects all islands

        // Test Case 2: Already all land
        int[][] grid2 = {
            {1, 1},
            {1, 1}
        };
        assert solution.largestIsland(grid2) == 4; // Already maximum size

        // Test Case 3: All water
        int[][] grid3 = {
            {0, 0},
            {0, 0}
        };
        assert solution.largestIsland(grid3) == 1; // Can only convert one cell

        // Test Case 4: Complex case with multiple islands
        int[][] grid4 = {
            {1, 1, 0, 0},
            {1, 0, 0, 1},
            {0, 0, 0, 1},
            {0, 1, 1, 1}
        };
        assert solution.largestIsland(grid4) == 7; // Can connect two islands

        System.out.println("All test cases passed!");
    }
}