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:
Create a dictionary to store the area of each connected component.
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.
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.
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)); } }