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 each cell which 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:
C++
#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; } |
Java
//Java implementation of the above approach: import java.util.*; public class LargestIslandSize { static Map<Integer, Integer> unmap = new HashMap<>(); // Depth-first search (DFS) function to calculate // the size of an island. static int dfs( int i, int j, int [][] grid, boolean [][] visited, int key) { int n = grid.length; // 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. static int largestIsland( int [][] grid) { int n = grid.length; int key = 2 ; boolean [][] visited = new boolean [n][n]; // 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] && grid[i][j] == 1 ) { int count = dfs(i, j, grid, visited, key); // Store island size in the map. unmap.put(key, count); key++; } } } int result = - 1 ; boolean [][] visited2 = new boolean [n][n]; // 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<Integer> st = new HashSet<>(); st.add(a); st.add(b); st.add(c); st.add(d); int res = 1 ; // Calculate the combined size // of neighboring islands. for ( int value : st) { res += unmap.getOrDefault(value, 0 ); } // Update the largest island size. result = Math.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; } // Driver code public static void main(String[] args) { // Input: Grid representing land (1) and // water (0) cells. 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); System.out.println( "Largest island size: " + largestIslandSize); } } //This code is contributed by chinmaya121221 |
Python3
unmap = {} # Dictionary to store island sizes # Depth-first search (DFS) function to calculate the size of an island def dfs(i, j, grid, visited, key): n = len (grid) # Base cases: Boundary checks, visited status, and water cells if i < 0 or j < 0 or i > = n or j > = n or visited[i][j] or grid[i][j] = = 0 : return 0 visited[i][j] = True # Recursively explore adjacent cells and accumulate the island size 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) grid[i][j] = key # Update the cell's value to the key representing the island return count # Function to find the size of the largest island in the grid def largestIsland(grid): n = len (grid) key = 2 visited = [[ False for _ in range (n)] for _ in range (n)] # Traverse the grid to identify and mark islands, and store their sizes in the map for i in range (n): for j in range (n): if not visited[i][j] and grid[i][j] = = 1 : count = dfs(i, j, grid, visited, key) unmap[key] = count key + = 1 result = - 1 visited2 = [[ False for _ in range (n)] for _ in range (n)] # Traverse the grid again to identify water cells and calculate the largest possible island for i in range (n): for j in range (n): if grid[i][j] = = 0 : # Check adjacent cells and gather island sizes from the map a = grid[i + 1 ][j] if i + 1 < n else 0 b = grid[i - 1 ][j] if i - 1 > = 0 else 0 c = grid[i][j + 1 ] if j + 1 < n else 0 d = grid[i][j - 1 ] if j - 1 > = 0 else 0 # Store unique island sizes around the current water cell st = set ([a, b, c, d]) res = 1 # Calculate the combined size of neighboring islands for val in st: res + = unmap.get(val, 0 ) result = max (result, res) # Update the largest island size # If no land cells were present (only water), return the size of the entire grid if result = = - 1 : return n * n return result # Main code 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 ] ] largest_island_size = largestIsland(grid) print (f "Largest island size: {largest_island_size}" ) |
C#
using System; using System.Collections.Generic; class Program { // Depth-first search (DFS) function to calculate // the size of an island. static int Dfs( int i, int j, int [][] grid, bool [][] visited, int key) { int n = grid.Length; // 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. static int LargestIsland( int [][] grid) { int n = grid.Length; int key = 2; bool [][] visited = new bool [n][]; for ( int i = 0; i < n; i++) { visited[i] = new bool [n]; } // Traverse the grid to identify and mark // islands, and store their sizes in the map. Dictionary< int , int > unmap = new Dictionary< int , int >(); for ( int i = 0; i < n; i++) { for ( int j = 0; j < n; j++) { if (!visited[i][j] && 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; bool [][] visited2 = new bool [n][]; for ( int i = 0; i < n; i++) { visited2[i] = new bool [n]; } // 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. HashSet< int > st = new HashSet< int >(); st.Add(a); st.Add(b); st.Add(c); st.Add(d); int res = 1; // Calculate the combined size of neighboring islands. foreach ( int value in st) { if (unmap.ContainsKey(value)) { res += unmap[value]; } } // Update the largest island size. result = Math.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; } static void Main() { int [][] grid = { new int [] { 1, 0, 1, 1, 0 }, new int [] { 1, 0, 0, 1, 0 }, new int [] { 0, 1, 1, 0, 1 }, new int [] { 1, 0, 1, 0, 1 }, new int [] { 0, 1, 0, 1, 0 } }; // Find and print the size of the largest island. int largestIslandSize = LargestIsland(grid); Console.WriteLine( "Largest island size: " + largestIslandSize); } } |
Javascript
// JavaScript implementation of the above approach: // Depth-first search (DFS) function to calculate // the size of an island. function dfs(i, j, grid, visited, key) { const n = grid.length; // 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. const 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. function largestIsland(grid) { const n = grid.length; let key = 2; const visited = new Array(n).fill( null ).map(() => new Array(n).fill( false )); // Traverse the grid to identify and mark // islands, and store their sizes in the map. const unmap = new Map(); for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { if (!visited[i][j] && grid[i][j] === 1) { const count = dfs(i, j, grid, visited, key); // Store island size in the map. unmap.set(key, count); key++; } } } let result = -1; const visited2 = new Array(n).fill( null ).map(() => new Array(n).fill( false )); // Traverse the grid again to identify water // cells and calculate the largest // possible island. for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { if (grid[i][j] === 0) { // Check adjacent cells and // gather island sizes from the map. const a = (i + 1 < n) ? grid[i + 1][j] : 0; const b = (i - 1 >= 0) ? grid[i - 1][j] : 0; const c = (j + 1 < n) ? grid[i][j + 1] : 0; const d = (j - 1 >= 0) ? grid[i][j - 1] : 0; // Store unique island sizes // around the current water cell. const st = new Set(); st.add(a); st.add(b); st.add(c); st.add(d); let res = 1; // Calculate the combined size // of neighboring islands. st.forEach((value) => { res += unmap.get(value) || 0; }); // Update the largest island size. result = Math.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; } // Driver code const 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. const largestIslandSize = largestIsland(grid); console.log( "Largest island size: " + largestIslandSize); |
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).
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’sInput: 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’sInput: 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++
// 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; } |
Java
// Java code for the above approach: import java.util.*; public class LargestIslandSize { // Depth-First Search (DFS) function to traverse // and count the size of an island. static int dfs( int i, int j, int [][] grid, boolean [][] visited) { int n = grid.length; // 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. static int largestIsland( int [][] grid) { int n = grid.length; 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. boolean [][] visited = new boolean [n][n]; // 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 = Math.max(result, res); } } } // If no disconnected islands were found, // return the area of the entire grid. if (result == - 1 ) { return n * n; } return result; } // Driver code public static void main(String[] args) { // Input: Grid representing land (1) // and water (0) cells. 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); System.out.println( "Largest island size: " + largestIslandSize); } } //This Code is Contributed by chinmaya121221 |
Python3
def dfs(i, j, grid, visited): n = len (grid) # Base cases for invalid cell positions # or already visited cells. if i < 0 or j < 0 or i > = n or j > = n or visited[i][j] or grid[i][j] = = 0 : return 0 visited[i][j] = True # Recursively explore neighboring cells. 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 def largestIsland(grid): n = len (grid) result = - 1 # Iterate through each cell in the grid. for i in range (n): for j in range (n): if grid[i][j] = = 0 : # Create a visited matrix to keep # track of visited cells during DFS. visited = [[ False ] * n for _ in range (n)] # Perform DFS from neighboring cells # to calculate island sizes. res1 = dfs(i + 1 , j, grid, visited) res2 = dfs(i - 1 , j, grid, visited) res3 = dfs(i, j + 1 , grid, visited) res4 = dfs(i, j - 1 , grid, visited) # Calculate the size of the new # island including the current cell. 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 # Driver code if __name__ = = "__main__" : # Input: Grid representing land (1) and water (0) cells. 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. largestIslandSize = largestIsland(grid) print ( "Largest island size:" , largestIslandSize) #Contributed by Aditi Tyagi |
C#
using System; using System.Collections.Generic; public class GFG { // Depth-First Search (DFS) function to traverse // and count the size of an island. static int Dfs( int i, int j, List<List< int >> grid, bool [][] visited) { int n = grid.Count; // 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. static int LargestIsland(List<List< int >> grid) { int n = grid.Count; 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. bool [][] visited = new bool [n][]; for ( int k = 0; k < n; k++) { visited[k] = new bool [n]; } // 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 = Math.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 public static void Main() { // Input: Grid representing land (1) // and water (0) cells. List<List< int >> grid = new List<List< int >> { new List< int > {1, 0, 1, 1, 0}, new List< int > {1, 0, 0, 1, 0}, new List< int > {0, 1, 1, 0, 1}, new List< int > {1, 0, 1, 0, 1}, new List< int > {0, 1, 0, 1, 0} }; // Find and print the size of the // largest island. int largestIslandSize = LargestIsland(grid); Console.WriteLine( "Largest island size: " + largestIslandSize); } } |
Javascript
function GFG(i, j, grid, visited) { const n = grid.length; // 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. const count = 1 + GFG(i + 1, j, grid, visited) + GFG(i - 1, j, grid, visited) + GFG(i, j + 1, grid, visited) + GFG(i, j - 1, grid, visited); return count; } // Function to find the size of the // largest island in the grid. function largestIsland(grid) { const n = grid.length; let result = -1; // Iterate through each cell in the grid. for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { if (grid[i][j] === 0) { // Create a visited matrix to keep track of // visited cells during DFS. const visited = new Array(n).fill( false ).map(() => new Array(n).fill( false )); // Perform DFS from neighboring cells to calculate // island size. const res1 = GFG(i + 1, j, grid, visited); const res2 = GFG(i - 1, j, grid, visited); const res3 = GFG(i, j + 1, grid, visited); const res4 = GFG(i, j - 1, grid, visited); // Calculate the size of the new island including // the current cell. const res = 1 + res1 + res2 + res3 + res4; result = Math.max(result, res); } } } // If no disconnected islands were found // return the area of the entire grid. if (result === -1) { return n * n; } return result; } // Driver code const 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. const largestIslandSize = largestIsland(grid); console.log( "Largest island size:" , largestIslandSize); |
Largest island size: 9
Time Complexity: O(n4)
Auxiliary Space: O(n2)