# 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)
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:
# 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++;

// elements and mark them
// as visited
DFS(M, i, j);
}
}
}
return count;
}

// function to mark all the
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;

// 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));
}
}```

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]