D
DevExCode

LeetCode 827: Making A Large Island Solution

Master LeetCode problem 827 (Making A Large Island), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation:

To solve this problem, we can follow these steps:

  1. Perform a Depth First Search (DFS) to label each island with a unique number and calculate its area. We can create a map to store the area of each island.
  2. Iterate over each '0' cell in the grid. For each '0' cell, check the unique island labels of its neighboring cells and calculate the total area if we change the '0' cell to '1'.
  3. Keep track of the maximum island area found during step 2.

Time Complexity: O(n^2) where n is the size of the grid. Space Complexity: O(n^2) for the island labeling map.

:

Solution Code

class Solution {
    public int largestIsland(int[][] grid) {
        int n = grid.length;
        Map<Integer, Integer> areaMap = new HashMap<>();
        int islandIndex = 2; // Starting index for island labeling

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    int area = dfs(grid, i, j, islandIndex);
                    areaMap.put(islandIndex, area);
                    islandIndex++;
                }
            }
        }

        int maxArea = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    Set<Integer> neighborIslands = new HashSet<>();
                    if (i > 0) neighborIslands.add(grid[i - 1][j]);
                    if (i < n - 1) neighborIslands.add(grid[i + 1][j]);
                    if (j > 0) neighborIslands.add(grid[i][j - 1]);
                    if (j < n - 1) neighborIslands.add(grid[i][j + 1]);

                    int totalArea = 1; // Current '0' cell turned to '1'
                    for (int island : neighborIslands) {
                        totalArea += areaMap.getOrDefault(island, 0);
                    }
                    maxArea = Math.max(maxArea, totalArea);
                }
            }
        }

        return maxArea == 0 ? n * n : maxArea;
    }

    private int dfs(int[][] grid, int i, int j, int islandIndex) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != 1) {
            return 0;
        }
        grid[i][j] = islandIndex;
        return 1 + dfs(grid, i - 1, j, islandIndex) + dfs(grid, i + 1, j, islandIndex)
                + dfs(grid, i, j - 1, islandIndex) + dfs(grid, i, j + 1, islandIndex);
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 827 (Making A Large Island)?

This page provides optimized solutions for LeetCode problem 827 (Making A Large Island) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 827 (Making A Large Island)?

The time complexity for LeetCode 827 (Making A Large Island) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 827 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 827 in Java, C++, or Python.

Back to LeetCode Solutions