Solution For Making A Large Island

The Making A Large Island problem on LeetCode is a medium-level problem in which we are given a 2D matrix of 0s and 1s representing an island, where 0 represents water and 1 represents land. The goal is to find the maximum area of an island by changing at most one 0 to 1.

To solve this problem, we can use a depth-first search (DFS) algorithm to traverse the island and find the area of each connected component (island). We can keep track of the areas of each connected component using a dictionary. Once we have the areas of all connected components, we can iterate over each 0 in the matrix and check if flipping that 0 to 1 will create a larger island. We can then return the maximum area of the island.

Here is a step-by-step approach to solve the problem:

1. Create a dictionary to store the area of each connected component.

2. Use DFS to traverse the island and find the area of each connected component. For this, we can start at each 1 in the matrix and recursively visit all its neighbors (up, down, left, right) that are also 1s. We can mark each visited cell as -1 to avoid revisiting it. While traversing each connected component, we can add its area to the dictionary.

3. Iterate over each 0 in the matrix and check if flipping that 0 to 1 will create a larger island. For this, we can check the area of each connected component that is adjacent to the 0. We can do this by checking the values of its neighboring cells (up, down, left, right) that are not marked as -1. If we find a neighboring cell with a value of 1, we can add its area to the area of the current connected component. If the resulting area is greater than the maximum area seen so far, we update the maximum area.

4. Return the maximum area of the island.

Here is the Python implementation of the above approach:

“`
class Solution:
def largestIsland(self, grid: List[List[int]]) -> int:

    # dictionary to store the area of each connected component
    area_dict = {}
    max_area = 0

    # DFS to traverse the island and find the area of each connected component
    def dfs(i, j, area):
        # check if current cell is within bounds and is a land cell
        if 0<=i<len(grid) and 0<=j<len(grid[0]) and grid[i][j]==1:
            # mark cell as visited
            grid[i][j] = -1
            # add cell to current connected component
            area += 1
            # recursive DFS to visit all neighboring land cells
            area = dfs(i-1, j, area)  # up
            area = dfs(i+1, j, area)  # down
            area = dfs(i, j-1, area)  # left
            area = dfs(i, j+1, area)  # right
        return area

    # iterate over each cell of the matrix
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == 1:
                # perform DFS to find the area of the connected component
                area = dfs(i, j, 0)
                # add area to dictionary
                area_dict[(i,j)] = area
                # update maximum area seen so far
                max_area = max(max_area, area)

    # iterate over each 0 in the matrix and check if flipping it to 1 creates a larger island
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == 0:
                # check area of each adjacent connected component
                neighbors = set()
                for x,y in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
                    if 0<=x<len(grid) and 0<=y<len(grid[0]) and grid[x][y]!=-1:
                        neighbors.add((x,y))
                # calculate total area if we flip current 0 to 1
                area = 1
                for neighbor in neighbors:
                    area += area_dict.get(neighbor, 0)
                # update maximum area seen so far
                max_area = max(max_area, area)

    return max_area

“`

The time complexity of the above algorithm is O(n^2) for iterating over each cell of the matrix and performing DFS for each connected component. The space complexity is also O(n^2) for storing the area of each connected component in a dictionary.

Step by Step Implementation For Making A Large Island

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int max_area = 0;
        for(int i = 0; i < grid.length; i++)
            for(int j = 0; j < grid[0].length; j++)
                if(grid[i][j] == 1)max_area = Math.max(max_area, AreaOfIsland(grid, i, j));
        return max_area;
    }
    
    public int AreaOfIsland(int[][] grid, int i, int j){
        if( i >= 0 && i < grid.length && j >= 0 && j < grid[0].length && grid[i][j] == 1){
            grid[i][j] = 0;
            return 1 + AreaOfIsland(grid, i+1, j) + AreaOfIsland(grid, i-1, j) + AreaOfIsland(grid, i, j-1) + AreaOfIsland(grid, i, j+1);
        }
        return 0;
    }
}

def largestIsland(grid):
    
    # keep track of the largest island size
    largest = 0
    
    # keep track of all the islands
    islands = []
    
    # iterate through the grid
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            
            # if we find an island
            if grid[i][j] == 1:
                
                # do a DFS to find the size of the island
                size = dfs(grid, i, j)
                
                # add the size of the island to our list
                islands.append(size)
                
                # update the largest island size
                largest = max(largest, size)
                
    # iterate through the grid again
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            
            # if we find an empty spot
            if grid[i][j] == 0:
                
                # keep track of the size of the new island
                new_island = 1
                
                # set of neighbors of empty spot
                neighbors = set([(i, j-1), (i, j+1), (i-1, j), (i+1, j)])
                
                # iterate through the neighbors
                for x, y in neighbors:
                    
                    # if the neighbor is on the grid and is an island
                    if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and grid[x][y] in islands:
                        
                        # increment the size of the new island
                        new_island += islands[grid[x][y] - 1]
                        
                # update the largest island size
                largest = max(largest, new_island)
                
    return largest


# helper function for DFS
def dfs(grid, i, j):
    
    # base case: out of bounds or not an island
    if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] == 0:
        return 0
    
    # mark the current spot as visited
    grid[i][j] = 0
    
    # recursive case: explore all neighbors
    return 1 + dfs(grid, i+1, j) + dfs(grid, i-1, j) + dfs(grid, i, j+1) + dfs(grid, i, j-1)

var largestIsland = function(grid) {
    
    // keep track of the number of islands
    let numOfIslands = 0;
    
    // keep track of the largest island
    let largestIsland = 0;
    
    // iterate through the grid
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[i].length; j++) {
            
            // if the current cell is an island
            if (grid[i][j] === 1) {
                
                // increment the number of islands
                numOfIslands++;
                
                // keep track of the size of the current island
                let islandSize = 0;
                
                // use DFS to find the size of the current island
                islandSize = getIslandSize(grid, i, j);
                
                // update the largest island
                largestIsland = Math.max(largestIsland, islandSize);
            }
        }
    }
    
    // if there is only one island, we cannot make a larger island
    if (numOfIslands === 1) {
        return largestIsland;
    }
    
    // iterate through the grid again
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[i].length; j++) {
            
            // if the current cell is water
            if (grid[i][j] === 0) {
                
                // keep track of the size of the island we can make
                let newIslandSize = 1;
                
                // iterate through the neighbors of the current cell
                for (let x = -1; x <= 1; x++) {
                    for (let y = -1; y <= 1; y++) {
                        
                        // if the neighbor is on the grid and is an island
                        if (i+x >= 0 && i+x < grid.length && j+y >= 0 && j+y < grid[i].length && grid[i+x][j+y] === 1) {
                            
                            // use DFS to find the size of the island
                            let islandSize = getIslandSize(grid, i+x, j+y);
                            
                            // update the size of the new island
                            newIslandSize += islandSize;
                        }
                    }
                }
                
                // update the largest island
                largestIsland = Math.max(largestIsland, newIslandSize);
            }
        }
    }
    
    return largestIsland;
};

// DFS function to find the size of an island
var getIslandSize = function(grid, i, j) {
    
    // base case - if the current cell is not an island or out of bounds, return 0
    if (i < 0 || i >= grid.length || j < 0 || j >= grid[i].length || grid[i][j] === 0) {
        return 0;
    }
    
    // set the current cell to visited
    grid[i][j] = 0;
    
    // increment the size of the island
    let size = 1;
    
    // iterate through the neighbors of the current cell
    for (let x = -1; x <= 1; x++) {
        for (let y = -1; y <= 1; y++) {
            
            // use DFS to find the size of the island
            size += getIslandSize(grid, i+x, j+y);
        }
    }
    
    return size;
};

int largestIsland(vector>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        int res = 0;
        int id = 2; // start from id 2
        vector area(n*m, 0);
        for(int i = 0; i < n; i++) {
                for(int j = 0; j < m; j++) {
                        if(grid[i][j] == 1) {
                                int cur = dfs(grid, i, j, area, id, n, m);
                                res = max(res, cur);
                                id++;
                        }
                }
        }
        for(int i = 0; i < n; i++) {
                for(int j = 0; j < m; j++) {
                        if(grid[i][j] == 0) {
                                set s;
                                int cur = 1;
                                for(int k = 0; k < 4; k++) {
                                        int ni = i + dirs[k];
                                        int nj = j + dirs[k+1];
                                        if(ni >= 0 && ni < n && nj >= 0 && nj < m && grid[ni][nj] > 1) {
                                                if(!s.count(grid[ni][nj])) {
                                                        s.insert(grid[ni][nj]);
                                                        cur += area[grid[ni][nj]];
                                                }
                                        }
                                }
                                res = max(res, cur);
                        }
                }
        }
        return res;
}

int dfs(vector>& grid, int i, int j, vector& area, int id, int n, int m) {
        if(i < 0 || i >= n || j < 0 || j >= m || grid[i][j] <= 0) return 0;
        if(grid[i][j] != 1) return area[grid[i][j]];
        int cur = 1;
        grid[i][j] = id;
        for(int k = 0; k < 4; k++) {
                cur += dfs(grid, i + dirs[k], j + dirs[k+1], area, id, n, m);
        }
        area[id] = cur;
        return cur;
}

using System; 
  
public class GFG { 
      
    // function to calculate the 
    // number of islands in the given 
    // 2D array 
    static int numIslands(int[,] M) 
    { 
          
        // stores the number of islands 
        int count = 0; 
          
        // iterate over the 2D array 
        for (int i = 0; i < M.GetLength(0); i++) 
        { 
            for (int j = 0; j < M.GetLength(1); j++) 
            { 
                  
                // if the current element 
                // is an island 
                if (M[i,j] == 1) 
                { 
                      
                    // increment the number of 
                    // islands by 1 
                    count++; 
                      
                    // check all the adjacent 
                    // elements and mark them 
                    // as visited 
                    DFS(M, i, j); 
                } 
            } 
        } 
        return count; 
    } 
      
    // function to mark all the 
    // adjacent elements as visited 
    static void DFS(int[,] M, int i, int j) 
    { 
          
        // check if the current element 
        // is a valid element or not 
        if (i < 0 || j < 0 || i >= M.GetLength(0) ||  
                                  j >= M.GetLength(1) ||  
                                                M[i,j] != 1) 
            return; 
              
        // mark the current element 
        // as visited 
        M[i,j] = 0; 
          
        // check all the adjacent 
        // elements 
        DFS(M, i + 1, j); 
        DFS(M, i - 1, j); 
        DFS(M, i, j + 1); 
        DFS(M, i, j - 1); 
    } 
      
    // Driver Code 
    public static void Main() 
    { 
          
        // 2D array representing 
        // the given matrix 
        int[,] M = { { 1, 1, 0, 0, 0 }, 
                     { 0, 1, 0, 0, 1 }, 
                     { 1, 0, 0, 1, 1 }, 
                     { 0, 0, 0, 0, 0 }, 
                     { 1, 0, 1, 0, 1 } }; 
          
        Console.Write(numIslands(M)); 
    } 
}