5

Maximum Connected group (Making A Large Island)

 1 year ago
source link: https://www.geeksforgeeks.org/maximum-connected-group-making-a-large-island/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

Maximum Connected group (Making A Large Island)

Given a binary matrix of size n x n, the task is to find the largest island after changing at most one cell from 0 to 1.

Note: An island is a 4-directionally (i.e, up, down, right, left) connected group of 1s.

Examples:

Input: grid = {{1 1},
{0 1}}
Output: 4
Explanation: By changing cell (2,1) ,we can obtain a connected group of 4 1’s

Input: grid = {{1 0 1},
{1 0 1},
{1 0 1}}
Output: 7
Explanation: By changing cell (3,2) ,we can obtain a connected group of 7 1’s

Input: grid = { { 1, 0, 1, 1, 0 },
{ 1, 0, 0, 1, 0 },
{ 0, 1, 1, 0, 1 },
{ 1, 0, 1, 0, 1 },
{ 0, 1, 0, 1, 0 } };
Output: 9

Naive approach: The basic way to solve the problem is as follows:

The idea to solve the problem is to use DFS. For each water cell (i.e, grid[i][j] = 0’s ) maximise the result by summation of all unique neighbour’s island size + 1 (i.e, we add 1 extra because we also have to convert the current water cell into land.

Follow the steps below to implement the above idea:

  • Iterate through each cell of the grid which represents water or 0’s:
  • Count the size of the unique island in its neighbors (up, down, left, right)
  • Maintain a variable say result to track the largest island size found.
  • Return the result

Below is the implementation of the above approach:

// C++ code for the above approach:
#include <bits/stdc++.h>
using namespace std;
// Depth-First Search (DFS) function to traverse
// and count the size of an island.
int dfs(int i, int j, vector<vector<int> >& grid,
vector<vector<bool> >& visited)
{
int n = grid.size();
// Base cases for invalid cell positions
// or already visited cells.
if (i < 0 || j < 0 || i >= n || j >= n || visited[i][j]
|| grid[i][j] == 0) {
return 0;
}
visited[i][j] = true;
// Recursively explore neighboring cells.
int count = 1 + dfs(i + 1, j, grid, visited)
+ dfs(i - 1, j, grid, visited)
+ dfs(i, j + 1, grid, visited)
+ dfs(i, j - 1, grid, visited);
return count;
}
// Function to find the size of the largest
// island in the grid.
int largestIsland(vector<vector<int> >& grid)
{
int n = grid.size();
int result = -1;
// Iterate through each cell in the grid.
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 0) {
// Create a visited matrix to keep
// track of visited cells during DFS.
vector<vector<bool> > visited(
n, vector<bool>(n, false));
// Perform DFS from neighboring
// cells to calculate island sizes.
int res1 = dfs(i + 1, j, grid, visited);
int res2 = dfs(i - 1, j, grid, visited);
int res3 = dfs(i, j + 1, grid, visited);
int res4 = dfs(i, j - 1, grid, visited);
// Calculate the size of the new
// island including the current cell.
int res = 1 + res1 + res2 + res3 + res4;
// Update the result with the
// maximum island size found so far.
result = max(result, res);
}
}
}
// If no disconnected islands were found,
// return the area of the entire grid.
if (result == -1) {
return n * n;
}
return result;
}
// Drivers code
int main()
{
// Input: Grid representing land (1)
// and water (0) cells.
vector<vector<int> > grid = { { 1, 0, 1, 1, 0 },
{ 1, 0, 0, 1, 0 },
{ 0, 1, 1, 0, 1 },
{ 1, 0, 1, 0, 1 },
{ 0, 1, 0, 1, 0 } };
// Find and print the size of the
// largest island.
int largestIslandSize = largestIsland(grid);
cout << "Largest island size: " << largestIslandSize
<< endl;
return 0;
}
Output
Largest island size: 9

Time Complexity: O(n4)
Auxiliary Space: O(n2)

Maximum Connected group using DFS:

The idea is to keep track of each island by some unique identity say key/name with its size. After this, go through eachcellwhich is water (i.e, matrix[i][j] == 0) and add the sizes of unique neighbour’s island into current size, finally maximize the current size in the result.

Follow the steps below to implement the above idea:

  • Initialize a result variable for storing the largest island.
  • Create an unordered map to store identity of each island with its sizes.
  • Explore each island and update the cell’s value with a unique key and finally store key and size of island in map.
  • Iterate through each cell of the grid. which represents water or 0’s:
  • Get sizes of neighboring islands from the map.
  • Calculate combined size of neighboring islands and the current cell.
  • Update the result with the maximum calculated size.

Below is the implementation of the above approach:

#include <bits/stdc++.h>
using namespace std;
// Initialize an unordered map to store island
// sizes with corresponding keys.
unordered_map<int, int> unmap;
// Depth-first search (DFS) function to calculate
// the size of an island.
int dfs(int i, int j, vector<vector<int> >& grid,
vector<vector<bool> >& visited, int key)
{
int n = grid.size();
// Base cases: Check for boundaries,
// visited status, and water (grid[i][j] == 0).
if (i < 0 || j < 0 || i >= n || j >= n || visited[i][j]
|| grid[i][j] == 0) {
return 0;
}
// Mark the current cell as visited.
visited[i][j] = true;
// Recursively explore adjacent cells and
// accumulate the island size.
int count = 1 + dfs(i + 1, j, grid, visited, key)
+ dfs(i - 1, j, grid, visited, key)
+ dfs(i, j + 1, grid, visited, key)
+ dfs(i, j - 1, grid, visited, key);
// Update the cell's value to the key
// representing the island.
grid[i][j] = key;
return count;
}
// Function to find the size of the largest
// island in the grid.
int largestIsland(vector<vector<int> >& grid)
{
int n = grid.size();
int key = 2;
vector<vector<bool> > visited(n,
vector<bool>(n, false));
// Traverse the grid to identify and mark
// islands, and store their sizes in the map.
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (visited[i][j] == false && grid[i][j] == 1) {
int count = dfs(i, j, grid, visited, key);
// Store island size in the map.
unmap[key] = count;
key++;
}
}
}
int result = -1;
vector<vector<bool> > visited2(n,
vector<bool>(n, false));
// Traverse the grid again to identify water
// cells and calculate the largest
// possible island.
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 0) {
// Check adjacent cells and
// gather island sizes from the map.
int a = (i + 1 < n) ? grid[i + 1][j] : 0;
int b = (i - 1 >= 0) ? grid[i - 1][j] : 0;
int c = (j + 1 < n) ? grid[i][j + 1] : 0;
int d = (j - 1 >= 0) ? grid[i][j - 1] : 0;
// Store unique island sizes
// around the current water cell.
set<int> st;
st.insert(a);
st.insert(b);
st.insert(c);
st.insert(d);
int res = 1;
// Calculate the combined size
// of neighboring islands.
for (auto it = st.begin(); it != st.end();
it++) {
res += unmap[*it];
}
// Update the largest island size.
result = max(result, res);
}
}
}
// If no land cells were present (only water),
// return the size of the entire grid.
if (result == -1) {
return n * n;
}
return result;
}
// Drivers code
int main()
{
// Input: Grid representing land (1) and
// water (0) cells.
vector<vector<int> > grid = { { 1, 0, 1, 1, 0 },
{ 1, 0, 0, 1, 0 },
{ 0, 1, 1, 0, 1 },
{ 1, 0, 1, 0, 1 },
{ 0, 1, 0, 1, 0 } };
// Find and print the size of the
// largest island.
int largestIslandSize = largestIsland(grid);
cout << "Largest island size: " << largestIslandSize
<< endl;
return 0;
}
Output
Largest island size: 9

Time Complexity: O(n2)

  • The two nested loops iterate through all cells in the grid, resulting in O(n2)iterations.
  • Inside the loops, constant time operations are performed for DFS exploration and island size calculations.
  • The overall time complexity is O(n2), where n is the size of the grid.

Auxiliary Space: O(n2)

  • The visited matrix requires O(n2) space.
  • The unordered map stores island sizes, potentially up to O(n^2) distinct islands.
  • Other variables and data structures used occupy constant space.
  • The overall space complexity is O(n2).

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK