hard Making A Large Island

Problem Statement

Given a 2D binary matrix of size n x n, return the integer representing the size of the largest island after changing at most 0 to 1.

Here, Island is defined as a 4-directionally connected group of 1s.

Examples

• Example 1:

  • Input:

    [[1, 0, 1, 0],
     [0, 1, 1, 0],
     [0, 0, 0, 1],
     [1, 1, 0, 0]]
    

  • Expected Output: 6
  • Justification: Converting the water cell at position (2,1) will connect two large islands (top right and bottom left) with a new land cell, creating an island of size 6.

• Example 2:

  • Input:

    [[1, 1, 1],
     [1, 0, 0],
     [0, 0, 1]]
    

  • Expected Output: 6
  • Justification: Changing the cell (1,2) into land will connect the top horizontal island with the bottom right cell, resulting in a single island of size 6.

• Example 3:

  • Input:

    [[0, 1, 0],
     [1, 0, 1],
     [0, 1, 0]]
    

  • Expected Output: 5
  • Justification: By converting the center cell (1,1) to land, all surrounding cells will connect, forming a cross-shaped island with 5 cells.

Constraints:

• n == grid.length
• n == grid[i].length
• 1 <= n <= 500
• grid[i][j] is either 0 or 1.

Solution

To solve this problem, we will first identify and label each connected land area with a unique identifier. For this, a depth-first search (DFS) is suitable as it can traverse through connected land cells effectively. By labeling each land area, we can quickly determine the size of each island and store this information.

After labeling, we will check each water cell in the grid. For each water cell, we will look at its neighboring cells and calculate the potential size of the island if this water cell is converted to land. The key here is to ensure that we only consider unique neighboring islands to avoid counting the same land area multiple times. By doing so, we can accurately determine the maximum island size that can be achieved by converting a single water cell to land. This approach is efficient as it reduces the problem to identifying and summing up unique neighboring islands around water cells.

Step-by-step Algorithm

• Initialization:
  • Create a map to store the size of each island, indexed by a unique identifier.
  • Set a variable maxIslandSize to 0, which will keep track of the maximum island size found.
  • Use a 2D array islandId to store the identifier for each cell in the grid.
  • Set an identifier id starting from 2 (since 0 and 1 are already used in the grid).
• Labeling Islands:
  • Iterate over each cell in the grid.
  • When a land cell (value 1) is encountered that has not yet been assigned an identifier:
    • Perform a DFS from this cell to label the entire connected island with the current id.
    • Increment id for the next island.
• DFS Function:
  • The DFS function labels all connected land cells with the same identifier.
  • It also counts the number of cells in the island and updates the map with the size of the island.
• Calculating Potential Island Size:
  • Iterate over the grid again, this time focusing on water cells (value 0).
  • For each water cell, check its four adjacent cells (up, down, left, right).
  • Maintain a set to store unique island identifiers of neighboring land cells.
  • Calculate the potential size of the island by converting the current water cell to land. This is done by summing the sizes of unique neighboring islands and adding 1 (for the current water cell).
  • Update maxIslandSize if this calculated size is larger.
• Final Step:
  • After iterating through all cells, return maxIslandSize as the result.

Algorithm Walkthrough

Let's walk through the algorithm using Example 1, where the input grid is:

[[1, 0, 1, 0],
 [0, 1, 1, 0],
 [0, 0, 0, 1],
 [1, 1, 0, 0]]

1. Initialize Data Structures:

   • The grid is a 4x4 matrix.
   • We use a map islandSizeMap to track the size of each island.
   • An islandId matrix stores the identifier of each island.
   • Initialize maxIslandSize as 0 and id as 2.

2. Labeling Islands with DFS:

   • Start iterating over the grid.
   • First land cell is at (0,0). Perform DFS, label it with id = 2. This is a single cell island; islandSizeMap[2] = 1.
   • Next land at (0,2), gets id = 3. islandSizeMap[3] = 3.
   • The next unvisited land starts at (2,3). Label these connected cells with id = 4. This island has 1 cell; islandSizeMap[4] = 1.
   • Finally, label the bottom left island starting at (3,0) with id = 5. This island has 2 cells; islandSizeMap[5] = 2.
   • The grid now looks like:

     [[2, 0, 3, 0],
      [0, 3, 3, 0],
      [0, 0, 0, 4],
      [5, 5, 0, 0]]
     

3. Calculating Potential Island Sizes:

   • Examine each water cell to determine the potential island size if converted to land.
   • For cell (0,1), we have neighboring islands with id = 2 and id = 3. Potential size = 1 (new land) + islandSizeMap[2] + islandSizeMap[3] = 1 + 1 + 3 = 5.
   • For cell (0,3), we have neighboring islands with id = 3. Potential size = 1 (new land) + islandSizeMap[3] = 1 + 3 = 4.
   • For cell (1,0), we have neighboring islands with id = 3 and id = 4. Potential size = 1 (new land) + islandSizeMap[3] + islandSizeMap[4] = 1 + 3 + 1 = 5.
   • For cell (1,3), we have neighboring islands with id = 2 and id = 3. Potential size = 1 (new land) + islandSizeMap[2] + islandSizeMap[3] = 1 + 1 + 3 = 5.
   • For cell (2,0), we have neighboring islands with id = 5. Potential size = 1 (new land) + islandSizeMap[5] = 1 + 2 = 3.
   • For cell (2,1), the neighbors are id = 4 and id = 5. Potential size = 1 (new land) + islandSizeMap[4] + islandSizeMap[5] = 1 + 3 + 2 = 6.
   • Perform similar calculations for other water cells.

4. Finding the Maximum Island Size:

   • The largest potential island size we find is 6 from cell (2,1).
   • Thus, maxIslandSize = 6.

Code

import java.util.*;

public class Solution {

  private int[][] grid;
  private boolean[][] visited;
  private int n; // Grid dimension
  private Map<Integer, Integer> islandSizeMap = new HashMap<>(); // Map to store island sizes

  // Main method to find the largest island after conversion
  public int largestIsland(int[][] grid) {
    this.grid = grid;
    n = grid.length;
    visited = new boolean[n][n]; // Visited array to keep track of visited cells
    int id = 2; // Starting ID for islands
    int maxIslandSize = 0; // Max island size found

    // Labeling each island with a unique identifier
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (grid[i][j] == 1 && !visited[i][j]) {
          int size = dfs(i, j, id); // Perform DFS to find island size
          islandSizeMap.put(id, size); // Store island size
          maxIslandSize = Math.max(maxIslandSize, size); // Update max island size
          id++; // Increment island ID
        }
      }
    }

    // Checking each water cell to calculate potential island size
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (grid[i][j] == 0) {
          maxIslandSize = Math.max(maxIslandSize, calculatePotentialSize(i, j)); // Update max island size
        }
      }
    }

    return maxIslandSize == 0 ? n * n : maxIslandSize; // Return max island size
  }

  // DFS function to label islands and calculate their sizes
  private int dfs(int x, int y, int id) {
    if (
      x < 0 || y < 0 || x >= n || y >= n || visited[x][y] || grid[x][y] == 0
    ) {
      return 0; // Boundary and visited check
    }
    visited[x][y] = true; // Mark as visited
    grid[x][y] = id; // Assign island ID
    int size = 1; // Initialize island size
    // Explore all four directions
    size += dfs(x + 1, y, id);
    size += dfs(x - 1, y, id);
    size += dfs(x, y + 1, id);
    size += dfs(x, y - 1, id);
    return size; // Return total island size
  }

  // Function to calculate the potential size of an island if a water cell is converted to land
  private int calculatePotentialSize(int x, int y) {
    Set<Integer> adjacentIslands = new HashSet<>(); // Set to store unique adjacent island IDs
    // Check all four neighboring cells
    if (x > 0) adjacentIslands.add(grid[x - 1][y]);
    if (y > 0) adjacentIslands.add(grid[x][y - 1]);
    if (x < n - 1) adjacentIslands.add(grid[x + 1][y]);
    if (y < n - 1) adjacentIslands.add(grid[x][y + 1]);

    int potentialSize = 1; // Include the current water cell
    // Sum sizes of all unique adjacent islands
    for (int islandId : adjacentIslands) {
      potentialSize += islandSizeMap.getOrDefault(islandId, 0);
    }
    return potentialSize; // Return potential island size
  }

  // Main method for testing
  public static void main(String[] args) {
    Solution solution = new Solution();
    // Test cases
    int[][] grid1 = {
      { 1, 0, 1, 0 },
      { 0, 1, 1, 0 },
      { 0, 0, 0, 1 },
      { 1, 1, 0, 0 },
    };
    System.out.println("Example 1: " + solution.largestIsland(grid1));

    int[][] grid2 = { { 1, 1, 1 }, { 1, 0, 0 }, { 0, 0, 1 } };
    System.out.println("Example 2: " + solution.largestIsland(grid2));

    int[][] grid3 = { { 0, 1, 0 }, { 1, 0, 1 }, { 0, 1, 0 } };
    System.out.println("Example 3: " + solution.largestIsland(grid3));
  }
}

Complexity Analysis

Time Complexity

• DFS Traversal: , where N is the grid dimension. DFS is performed for each cell in the grid.
• Calculating Potential Island Size: Also , as it involves checking adjacent cells for each grid cell.
• Overall Time Complexity: , since both steps are linear with respect to the number of cells.

Space Complexity

Space used for the visited 2D array and the islandSizeMap, both of which are proportional to the grid size.

• DFS Stack Space: in the worst case (for a fully connected grid).
• Overall Space Complexity: , primarily due to the 2D array and the recursion stack space.