Given a grid[][] containing 0s and 1s, where ‘0’ represents water and ‘1’ represents the land. Given that an island is a group of land (1s) surrounded by water (0s) on all sides.
The task is to find the distance between the two closest islands such that:
- Distance between two islands is the minimum number of ‘0’ between two islands.
- Only 4 – directional movement is allowed.
- There are at least 2 islands present in the grid.
Examples:
Input: grid = {{1, 1, 0, 1, 1},
{1, 1, 0, 0, 0},
{0, 0, 0, 0, 0},
{0, 0, 1, 1, 1}}
Output: 1
Explanation: There are three islands present in the grid.
Nearest pair of islands have only 1 zero (bolded in input grid) in between them.Input: grid = {{1, 0, 0, 0, 1},
{1, 1, 0, 0, 0},
{0, 0, 0, 0, 0},
{0, 0, 1, 1, 1}}
Output: 2
Explanation: There are three islands present in the grid.
Nearest pair of islands have 2 zeroes in between them (depicted by bold 0 in input grid).
In this case there are multiple pair of islands having a distance of 2 between them.
Naive Approach:
The intuition is to find minimum distance between every possible pair of islands and return the minimum of all the distances, using DFS.
To find minimum distance between 2 islands follow the below steps:
- Store the coordinates of every islands separately in List / vector.
- Create a boolean visited array to mark if an element has been visited.
- Traverse the grid and if an element is ‘1’ and unvisited then call dfs to get all the elements corresponding island
- Store coordinates of this island in list.
- Find the minimum distance between every pair of islands in the list.
- For every pair of island in list find the minimum distance between them.
- distance between 2 islands will be the minimum distance between every pair of points in both islands.
- For every pair of island in list find the minimum distance between them.
- Return the minimum of all the distances between islands.
Below is the code for the implementation of approach:
C++
// CPP code to implement the approach#include <bits/stdc++.h>using namespace std;int row;int col;// Function to check if// a point is inside gridbool isValid(int x, int y){ if (x < 0 || x >= row || y < 0 || y >= col) return false; return true;}int dirx[] = { 0, 1, 0, -1 };int diry[] = { 1, 0, -1, 0 };void dfs(vector <vector<bool>> &visited, vector <vector<int>> &grid, int i, int j, vector <pair <int,int> > &island){ visited[i][j] = true; island.push_back({i,j}); for (int idx = 0; idx < 4; idx++) { int x = i + dirx[idx]; int y = j + diry[idx]; if (isValid(x, y) && grid[x][y] == 1 && !visited[x][y]) { dfs(visited, grid, x, y, island); } }}// Function to find and// store all islands in listvector <vector <pair <int,int> > >findIslands(vector <vector<int>> &grid){ vector <vector <bool>> visited(row,vector <bool> (col,false)); vector <vector <pair <int,int> > > list; for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { if (grid[i][j] == 1 && !visited[i][j]) { vector <pair <int,int> > island; dfs(visited, grid, i, j, island); list.push_back(island); } } } return list;}// Function to find min distance// between 2 islandsint findDistance(vector <pair <int,int> > &island1, vector <pair <int,int> > &island2){ int dist = INT_MAX; for (int i = 0; i < island1.size(); i++) { pair <int,int> point1 = island1[i]; for (int j = 0; j < island2.size(); j++) { pair <int,int> point2 = island2[j]; int distp1p2 = abs(point1.first - point2.first) + abs(point1.second - point2.second) - 1; dist = min(dist, distp1p2); } } return dist;}// Function to find closest distancevoid closestDistance(vector <vector<int>> &grid){ row = grid.size(); col = grid[0].size(); // List of coordinates // of all the islands vector <vector<pair <int,int>> > list = findIslands(grid); // Number of islands int n = list.size(); // Variable to store // minimum of all distances int ans = INT_MAX; for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { vector <pair <int,int> > island1 = list[i]; vector <pair <int,int> > island2 = list[j]; int dist = findDistance(island1, island2); ans = min(dist, ans); } } cout<<ans<<endl;}int main(){ vector <vector <int>> grid = { { 1, 0, 0, 0, 1 }, { 1, 1, 0, 0, 0 }, { 0, 0, 0, 0, 0 }, { 0, 0, 1, 1, 1 } }; closestDistance(grid); return 0;}// This code is contributed by Sachin Sahara (sachin801) |
Java
// Java code to implement the approachimport java.util.*;class GFG { static int row; static int col; // A class to represent coordinates of // element in matrix static class Pair { int x; int y; Pair(int x, int y) { this.x = x; this.y = y; } } // Function to find closest distance static void closestDistance(int[][] grid) { row = grid.length; col = grid[0].length; // List of coordinates // of all the islands ArrayList<ArrayList<Pair> > list = findIslands(grid); // Number of islands int n = list.size(); // Variable to store // minimum of all distances int ans = Integer.MAX_VALUE; for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { ArrayList<Pair> island1 = list.get(i); ArrayList<Pair> island2 = list.get(j); int dist = findDistance(island1, island2); ans = Math.min(dist, ans); } } System.out.println(ans); } // Function to find and // store all islands in list static ArrayList<ArrayList<Pair> > findIslands(int[][] grid) { boolean[][] visited = new boolean[row][col]; ArrayList<ArrayList<Pair> > list = new ArrayList<>(); for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { if (grid[i][j] == 1 && !visited[i][j]) { ArrayList<Pair> island = new ArrayList<>(); dfs(visited, grid, i, j, island); list.add(island); } } } return list; } // Function to find min distance // between 2 islands static int findDistance(ArrayList<Pair> island1, ArrayList<Pair> island2) { int dist = Integer.MAX_VALUE; for (int i = 0; i < island1.size(); i++) { Pair point1 = island1.get(i); for (int j = 0; j < island2.size(); j++) { Pair point2 = island2.get(j); int distp1p2 = Math.abs(point1.x - point2.x) + Math.abs(point1.y - point2.y) - 1; dist = Math.min(dist, distp1p2); } } return dist; } static int[] dirx = { 0, 1, 0, -1 }; static int[] diry = { 1, 0, -1, 0 }; static void dfs(boolean[][] visited, int[][] grid, int i, int j, ArrayList<Pair> island) { visited[i][j] = true; island.add(new Pair(i, j)); for (int idx = 0; idx < 4; idx++) { int x = i + dirx[idx]; int y = j + diry[idx]; if (isValid(x, y) && grid[x][y] == 1 && !visited[x][y]) { dfs(visited, grid, x, y, island); } } } // Function to check if // a point is inside grid static boolean isValid(int x, int y) { if (x < 0 || x >= row || y < 0 || y >= col) return false; return true; } // Driver code public static void main(String[] args) { int[][] grid = { { 1, 0, 0, 0, 1 }, { 1, 1, 0, 0, 0 }, { 0, 0, 0, 0, 0 }, { 0, 0, 1, 1, 1 } }; closestDistance(grid); }} |
Python3
# A class to represent coordinates of# element in matrixclass Pair: def __init__(self, x, y): self.x = x self.y = y# Function to find closest distancedef closestDistance(grid, row, col): # List of coordinates of all the islands list = findIslands(grid, row, col) # Number of islands n = len(list) # Variable to store minimum of all distances ans = float('inf') for i in range(n - 1): for j in range(i + 1, n): island1 = list[i] island2 = list[j] dist = findDistance(island1, island2) ans = min(dist, ans) print(ans)# Function to find and store all islands in listdef findIslands(grid, row, col): visited = [[False for j in range(col)] for i in range(row)] list = [] for i in range(row): for j in range(col): if grid[i][j] == 1 and not visited[i][j]: island = [] dfs(visited, grid, i, j, island, row, col) list.append(island) return list# Function to find min distance between 2 islandsdef findDistance(island1, island2): dist = float('inf') for i in range(len(island1)): point1 = island1[i] for j in range(len(island2)): point2 = island2[j] distp1p2 = abs(point1.x - point2.x) + abs(point1.y - point2.y) - 1 dist = min(dist, distp1p2) return distdirx = [0, 1, 0, -1]diry = [1, 0, -1, 0]def dfs(visited, grid, i, j, island, row, col): visited[i][j] = True island.append(Pair(i, j)) for idx in range(4): x = i + dirx[idx] y = j + diry[idx] if isValid(x, y, row, col) and grid[x][y] == 1 and not visited[x][y]: dfs(visited, grid, x, y, island, row, col)# Function to check if a point is inside griddef isValid(x, y, row, col): if x < 0 or x >= row or y < 0 or y >= col: return False return Truegrid = [[1, 0, 0, 0, 1], [1, 1, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 1, 1, 1]]closestDistance(grid, len(grid), len(grid[0])) |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;public class GFG { static int row; static int col; // A class to represent coordinates of // element in matrix class Pair { public int x; public int y; public Pair(int x, int y) { this.x = x; this.y = y; } } // Function to find closest distance static void closestDistance(int[,] grid) { row = grid.GetLength(0); col = grid.GetLength(1); // List of coordinates // of all the islands List<List<Pair> > list = findIslands(grid); // Number of islands int n = list.Count; // Variable to store // minimum of all distances int ans = int.MaxValue; for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { List<Pair> island1 = list[i]; List<Pair> island2 = list[j]; int dist = findDistance(island1, island2); ans = Math.Min(dist, ans); } } Console.WriteLine(ans); } // Function to find and // store all islands in list static List<List<Pair> > findIslands(int[,] grid) { bool[,] visited = new bool[row,col]; List<List<Pair> > list = new List<List<Pair>>(); for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { if (grid[i,j] == 1 && !visited[i,j]) { List<Pair> island = new List<Pair>(); dfs(visited, grid, i, j, island); list.Add(island); } } } return list; } // Function to find min distance // between 2 islands static int findDistance(List<Pair> island1, List<Pair> island2) { int dist = int.MaxValue; for (int i = 0; i < island1.Count; i++) { Pair point1 = island1[i]; for (int j = 0; j < island2.Count; j++) { Pair point2 = island2[j]; int distp1p2 = Math.Abs(point1.x - point2.x) + Math.Abs(point1.y - point2.y) - 1; dist = Math.Min(dist, distp1p2); } } return dist; } static int[] dirx = { 0, 1, 0, -1 }; static int[] diry = { 1, 0, -1, 0 }; static void dfs(bool[,] visited, int[,] grid, int i, int j, List<Pair> island) { visited[i,j] = true; island.Add(new Pair(i, j)); for (int idx = 0; idx < 4; idx++) { int x = i + dirx[idx]; int y = j + diry[idx]; if (isValid(x, y) && grid[x,y] == 1 && !visited[x,y]) { dfs(visited, grid, x, y, island); } } } // Function to check if // a point is inside grid static bool isValid(int x, int y) { if (x < 0 || x >= row || y < 0 || y >= col) return false; return true; } // Driver code public static void Main(String[] args) { int[,] grid = { { 1, 0, 0, 0, 1 }, { 1, 1, 0, 0, 0 }, { 0, 0, 0, 0, 0 }, { 0, 0, 1, 1, 1 } }; closestDistance(grid); }}// This code is contributed by 29AjayKumar |
Javascript
// Javascript code to implement the approach var row, col; // A class to represent coordinates of // element in matrix class Pair{ constructor(x, y) { this.x = x; this.y = y; } } // Function to find closest distance function closestDistance(grid) { row = grid.length; col = grid[0].length; // List of coordinates // of all the islands var list = findIslands(grid); // Number of islands n = list.length; // Variable to store // minimum of all distances ans = Number.MAX_SAFE_INTEGER; for (let i = 0 ; i < n - 1 ; i++) { for (let j = i + 1 ; j < n ; j++) { island1 = list[i]; island2 = list[j]; dist = findDistance(island1, island2); ans = Math.min(dist, ans); } } console.log(ans); } // Function to find and // store all islands in list function findIslands(grid) { var visited = new Array(row); for(let i = 0 ; i < row ; i++){ visited[i] = new Array(col) for(let j = 0 ; j < col ; j++){ visited[i][j] = false } } var list = new Array(); for (let i = 0 ; i < row ; i++) { for (let j = 0 ; j < col ; j++) { if (grid[i][j] == 1 && !visited[i][j]) { var island = new Array() dfs(visited, grid, i, j, island) list.push(island) } } } return list } // Function to find min distance // between 2 islands function findDistance(island1, island2) { var dist = Number.MAX_SAFE_INTEGER; for (let i = 0 ; i < island1.length ; i++) { var point1 = island1[i]; for (let j = 0 ; j < island2.length ; j++) { var point2 = island2[j]; var distp1p2 = Math.abs(point1.x - point2.x) + Math.abs(point1.y - point2.y) - 1; dist = Math.min(dist, distp1p2); } } return dist; } var dirx = [ 0, 1, 0, -1 ]; var diry = [ 1, 0, -1, 0 ]; function dfs(visited, grid, i, j, island) { visited[i][j] = true; island.push(new Pair(i, j)); for (let idx = 0; idx < 4; idx++) { var x = i + dirx[idx]; var y = j + diry[idx]; if (isValid(x, y) && grid[x][y] == 1 && !visited[x][y]) { dfs(visited, grid, x, y, island); } } } // Function to check if // a point is inside grid function isValid(x, y) { if (x < 0 || x >= row || y < 0 || y >= col){ return false; } return true; } // Driver code var grid = [ [ 1, 0, 0, 0, 1 ], [ 1, 1, 0, 0, 0 ], [ 0, 0, 0, 0, 0 ], [ 0, 0, 1, 1, 1 ] ]; closestDistance(grid); // This code is contributed by subhamgoyal2014. |
Output
2
Time Complexity: O(N4)
Auxiliary Space: O(N2)
Efficient Approach:
The idea is that instead of finding distance between each island pair from the naive approach, optimize the task using Depth-first-search and breadth-first-search traversal techniques for individual operations, as mentioned below:
- First find all islands in the Grid using DFS
- Then find the minimum distance island pair among these, using BFS.
Follow the steps to solve the problem using the above efficient approach:
- Create two 2d arrays ‘visited’ and ‘distance’ initialized by 0. Distance array will be to store the distance to nearest island.
- Traverse the grid and if an element is ‘1’ then call dfs to mark the corresponding element in visited array by any number other than 0.
- Mark each island in the visited array by different numbers.
- While doing dfs traversal simultaneously add node representing this element in queue which will be used in bfs.
- Use the queue created in previous steps for bfs traversal and expand every island level by level.
- if the neighboring element in grid is not marked visited then mark it visited with the same number as that of current node in visited array.
- Store distance of {current node + 1} in the distance array for neighboring unvisited element.
- else if neighboring element in grid is already marked visited with some number other than that of current node in visited array.
- return distance of current element + distance of neighboring element.
- if the neighboring element in grid is not marked visited then mark it visited with the same number as that of current node in visited array.
Below is the code for the implementation of approach:
C++
// CPP code to implement the approach#include <bits/stdc++.h>using namespace std;int row;int col;struct Pair { int x; int y; int identity; Pair(int x, int y, int identity) { this->x = x; this->y = y; this->identity = identity; }};// Function to check if// a point is inside gridbool isValid(int x, int y){ if (x < 0 || x >= row || y < 0 || y >= col) return false; return true;}int dirx[] = { 0, 1, 0, -1 };int diry[] = { 1, 0, -1, 0 };// Dfs function to add all island elements// In queue and marking them visited with idvoid dfs(vector <vector<int>> &grid, vector <vector<int>> &visited, queue <Pair> &q, int i, int j, int id){ visited[i][j] = id; Pair p1(i, j, id); q.push(p1); for (int idx = 0; idx < 4; idx++) { int x = i + dirx[idx]; int y = j + diry[idx]; if (isValid(x, y) && grid[x][y] == 1 && visited[x][y] == 0) { dfs(grid, visited, q, x, y, id); } }}// Bfs function to expand every island and// Maintaining distance arrayint bfs(vector <vector<int>> &grid, vector <vector<int>> & visited, vector <vector<int>> & distance, queue<Pair> &q){ while ( !q.empty() ) { Pair p = q.front(); q.pop(); for (int i = 0; i < 4; i++) { int x = p.x + dirx[i]; int y = p.y + diry[i]; if (isValid(x, y) && visited[x][y] == 0) { q.push(Pair(x, y, p.identity)); distance[x][y] = distance[p.x][p.y] + 1; visited[x][y] = p.identity; } else if (isValid(x, y) && visited[x][y] != 0 && visited[x][y] != visited[p.x][p.y]) { return distance[x][y] + distance[p.x][p.y]; } } } return -1;}// Function to find closest distancevoid closestDistance(vector <vector <int>> &grid){ row = grid.size(); col = grid[0].size(); int id = 1; queue <Pair> q; vector <vector <int>> visited(row,vector <int>(col,0)); // Distance array to store distance // From nearest island vector <vector <int>> distance(row,vector <int>(col,0)); for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { if (grid[i][j] == 1 && visited[i][j] == 0) { dfs(grid, visited, q, i, j, id); id++; } } } // To store minimal distance // b/w closest islands int ans = bfs(grid, visited, distance, q); cout << ans << endl;}int main(){ vector <vector <int>> grid = { { 1, 0, 0, 0, 1 }, { 1, 1, 0, 0, 0 }, { 0, 0, 0, 0, 0 }, { 0, 0, 1, 1, 1 } }; closestDistance(grid); return 0;}// This code is contributed by Sachin Sahara (sachin801) |
Java
// Java code to implement the approachimport java.util.*;class GFG { static int row; static int col; // A class to represent coordinates of // element in matrix static class Pair { int x; int y; int identity; Pair(int x, int y, int identity) { this.x = x; this.y = y; this.identity = identity; } } // Function to find closest distance static void closestDistance(int[][] grid) { row = grid.length; col = grid[0].length; int id = 1; Queue<Pair> q = new ArrayDeque<Pair>(); int[][] visited = new int[row][col]; // Distance array to store distance // From nearest island int[][] distance = new int[row][col]; for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { if (grid[i][j] == 1 && visited[i][j] == 0) { dfs(grid, visited, q, i, j, id); id++; } } } // To store minimal distance // b/w closest islands int ans = bfs(grid, visited, distance, q); System.out.println(ans); } static int[] dirx = { 0, 1, 0, -1 }; static int[] diry = { 1, 0, -1, 0 }; // Dfs function to add all island elements // In queue and marking them visited with id static void dfs(int[][] grid, int[][] visited, Queue<Pair> q, int i, int j, int id) { visited[i][j] = id; q.add(new Pair(i, j, id)); for (int idx = 0; idx < 4; idx++) { int x = i + dirx[idx]; int y = j + diry[idx]; if (isValid(x, y) && grid[x][y] == 1 && visited[x][y] == 0) { dfs(grid, visited, q, x, y, id); } } } // Bfs function to expand every island and // Maintaining distance array static int bfs(int[][] grid, int[][] visited, int[][] distance, Queue<Pair> q) { while (q.size() != 0) { Pair p = q.remove(); for (int i = 0; i < 4; i++) { int x = p.x + dirx[i]; int y = p.y + diry[i]; if (isValid(x, y) && visited[x][y] == 0) { q.add(new Pair(x, y, p.identity)); distance[x][y] = distance[p.x][p.y] + 1; visited[x][y] = p.identity; } else if (isValid(x, y) && visited[x][y] != 0 && visited[x][y] != visited[p.x][p.y]) { return distance[x][y] + distance[p.x][p.y]; } } } return -1; } // Function to check if point // Is inside grid static boolean isValid(int x, int y) { if (x < 0 || x >= row || y < 0 || y >= col) return false; return true; } // Driver Code public static void main(String[] args) { int[][] grid = { { 1, 0, 0, 0, 1 }, { 1, 1, 0, 0, 0 }, { 0, 0, 0, 0, 0 }, { 0, 0, 1, 1, 1 } }; closestDistance(grid); }} |
Python3
# python code to implement the approachfrom collections import deque# Function to find closest distancedef closestDistance(grid): row = len(grid) col = len(grid[0]) id = 1 q = deque() visited = [[0 for j in range(col)] for i in range(row)] # Distance array to store distance # From nearest island distance = [[0 for j in range(col)] for i in range(row)] dirx = [0, 1, 0, -1] diry = [1, 0, -1, 0] # Function to check if # a point is inside grid def isValid(x, y): return 0 <= x < row and 0 <= y < col # Dfs function to add all island elements # In queue and marking them visited with id def dfs(grid, visited, q, i, j, id): visited[i][j] = id p1 = (i, j, id) q.append(p1) for idx in range(4): x = i + dirx[idx] y = j + diry[idx] if isValid(x, y) and grid[x][y] == 1 and visited[x][y] == 0: dfs(grid, visited, q, x, y, id) for i in range(row): for j in range(col): if grid[i][j] == 1 and visited[i][j] == 0: dfs(grid, visited, q, i, j, id) id += 1 # Bfs function to expand every island and # Maintaining distance array def bfs(grid, visited, distance, q): while q: i, j, identity = q.popleft() for i in range(4): x = i + dirx[i] y = j + diry[i] if isValid(x, y) and visited[x][y] == 0: q.append((x, y, identity)) distance[x][y] = distance[i][j] + 1 visited[x][y] = identity elif isValid(x, y) and visited[x][y] != 0 and visited[x][y] != identity: return distance[x][y] + distance[i][j] return -1 # To store minimal distance # b/w closest islands ans = bfs(grid, visited, distance, q) print(ans)# Driver Codegrid = [ [1, 0, 0, 0, 1], [1, 1, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 1, 1, 1]]closestDistance(grid)# This code is contributed by Prasad Kandekar (prasad264) |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;public class GFG { static int row; static int col; // A class to represent coordinates of // element in matrix public class Pair { public int x; public int y; public int identity; public Pair(int x, int y, int identity) { this.x = x; this.y = y; this.identity = identity; } } // Function to find closest distance public static void ClosestDistance(int[][] grid) { row = grid.Length; col = grid[0].Length; int id = 1; Queue<Pair> q = new Queue<Pair>(); int[][] visited = new int[row][]; for (int i = 0; i < row; i++) { visited[i] = new int[col]; } // Distance array to store distance // From nearest island int[][] distance = new int[row][]; for (int i = 0; i < row; i++) { distance[i] = new int[col]; } for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { if (grid[i][j] == 1 && visited[i][j] == 0) { Dfs(grid, visited, q, i, j, id); id++; } } } // To store minimal distance // b/w closest islands int ans = bfs(grid, visited, distance, q); Console.WriteLine(ans); } static int[] dirx = { 0, 1, 0, -1 }; static int[] diry = { 1, 0, -1, 0 }; // Dfs function to add all island elements // In queue and marking them visited with id public static void Dfs(int[][] grid, int[][] visited, Queue<Pair> q, int i, int j, int id) { visited[i][j] = id; q.Enqueue(new Pair(i, j, id)); for (int idx = 0; idx < 4; idx++) { int x = i + dirx[idx]; int y = j + diry[idx]; if (IsValid(x, y) && grid[x][y] == 1 && visited[x][y] == 0) { Dfs(grid, visited, q, x, y, id); } } } // Bfs function to expand every island and // Maintaining distance array static int bfs(int[][] grid, int[][] visited, int[][] distance, Queue<Pair> q) { while (q.Count != 0) { Pair p = q.Dequeue(); for (int i = 0; i < 4; i++) { int x = p.x + dirx[i]; int y = p.y + diry[i]; if (IsValid(x, y) && visited[x][y] == 0) { q.Enqueue(new Pair(x, y, p.identity)); distance[x][y] = distance[p.x][p.y] + 1; visited[x][y] = p.identity; } else if (IsValid(x, y) && visited[x][y] != 0 && visited[x][y] != visited[p.x][p.y]) { return distance[x][y] + distance[p.x][p.y]; } } } return -1; } // Function to check if point // Is inside grid static bool IsValid(int x, int y) { if (x < 0 || x >= row || y < 0 || y >= col) return false; return true; } // Driver Code static public void Main(string[] args) { int[][] grid = { new int[] { 1, 0, 0, 0, 1 }, new int[] { 1, 1, 0, 0, 0 }, new int[] { 0, 0, 0, 0, 0 }, new int[] { 0, 0, 1, 1, 1 } }; ClosestDistance(grid); }}// This Code is Contributed by Prasad Kandekar(prasad264) |
Javascript
// JavaScript code to implement the approachvar row = null;var col = null;class Pair { constructor(x, y, identity) { this.x = x; this.y = y; this.identity = identity; }}// Function to check if// a point is inside gridfunction isValid(x, y) { if (x < 0 || x >= row || y < 0 || y >= col) { return false; } return true;}const dirx = [0, 1, 0, -1];const diry = [1, 0, -1, 0];// Dfs function to add all island elements// In queue and marking them visited with idfunction dfs(grid, visited, q, i, j, id) { visited[i][j] = id; var p1 = new Pair(i, j, id); q.push(p1); for (var idx = 0; idx < 4; idx++) { var x = i + dirx[idx]; var y = j + diry[idx]; if (isValid(x, y) && grid[x][y] === 1 && visited[x][y] === 0) { dfs(grid, visited, q, x, y, id); } }}// Bfs function to expand every island and// Maintaining distance arrayfunction bfs(grid, visited, distance, q) { while (q.length > 0) { var p = q.shift(); for (var i = 0; i < 4; i++) { var x = p.x + dirx[i]; var y = p.y + diry[i]; if (isValid(x, y) && visited[x][y] === 0) { q.push(new Pair(x, y, p.identity)); distance[x][y] = distance[p.x][p.y] + 1; visited[x][y] = p.identity; } else if (isValid(x, y) && visited[x][y] !== 0 && visited[x][y] !== visited[p.x][p.y]) { return distance[x][y] + distance[p.x][p.y]; } } } return -1;}// Function to find closest distancefunction closestDistance(grid) { row = grid.length; col = grid[0].length; var id = 1; var q = []; var visited = []; for (var i = 0; i < row; i++) { visited[i] = Array(col).fill(0); } // Distance array to store distance // From nearest island var distance = []; for (var i = 0; i < row; i++) { distance[i] = Array(col).fill(0); } for (var i = 0; i < row; i++) { for (var j = 0; j < col; j++) { if (grid[i][j] === 1 && visited[i][j] === 0) { dfs(grid, visited, q, i, j, id); id++; } } } // To store minimal distance // b/w closest islands var ans = bfs(grid, visited, distance, q); console.log(ans);}// Driver Codevar grid = [ [1, 0, 0, 0, 1], [1, 1, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 1, 1, 1] ];closestDistance(grid);// This code is contributed by Prasad Kandekar (prasad264) |
Output
2
Time Complexity: O(N2)
Auxiliary Space: O(N2)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
