Solution For As Far From Land As Possible
As Far From Land As Possible is a question on LeetCode, which is a platform that provides coding challenges to software developers. The problem statement is quite straightforward:
Given an n x n grid containing only 0s and 1s, where 0 represents water and 1 represents land, find the distance of the nearest land cell from each water cell. The distance between two adjacent land cells is 1 unit. You can assume that there is at least one land cell.
In other words, we need to find the distance of the nearest land cell for each water cell. We can use breadth-first search (BFS) to solve this problem efficiently.
Here’s the step-by-step solution to this problem:
Step 1: Create a queue to store the position of all the water cells in the grid.
Step 2: Initialize a visited matrix of the same size as the grid and mark all the land cells as visited.
Step 3: For all the water cells in the queue, perform a BFS operation and find the distance to each land cell. We start from each water cell and visit all its neighbors (up, down, left, right) one by one. If a neighbor cell is a land cell, we mark it as visited, and the distance to it is 1. If a neighbor cell is a water cell and not yet visited, we mark it as visited and add it to the queue along with its distance.
Step 4: Repeat step 3 until the queue becomes empty. At the end of each BFS operation, we update the minimum distance from the water cell to any land cell.
Step 5: Once all the BFS operations are complete, return the maximum distance found in the visited matrix. The result will be the answer to the problem.
Here’s the Python code for the same:
from collections import deque
def maxDistance(grid):
q = deque([])
visited = [[0 for j in range(len(grid))] for i in range(len(grid))]
# loop through the grid, starting from every land cells
for i in range(len(grid)):
for j in range(len(grid)):
if grid[i][j] == 1:
visited[i][j] = 1
q.append((i,j,0))
# handle case if there were no land cells
if not q or len(q) == len(grid)**2:
return -1
# perform BFS
while q:
i, j, dis = q.popleft()
# check all neighbors of current cell
for x, y in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
if x<0 or y<0 or x>=len(grid) or y>=len(grid):
continue
if not visited[x][y]:
visited[x][y] = 1
q.append((x,y,dis+1))
# update the grid with the distance to the nearest land
grid[x][y] = min(grid[x][y], dis+1)
# find the maximum distance
maxDis = 0
for i in range(len(grid)):
for j in range(len(grid)):
# if there is a water cell
if grid[i][j] == 0:
maxDis = max(maxDis, visited[i][j])
return maxDis
This solution has a time complexity of O(n^2), where n is the size of the grid.
Overall, this is an effective solution to the As Far From Land As Possible problem on LeetCode.
Step by Step Implementation For As Far From Land As Possible
class Solution { public int maxDistance(int[][] grid) { //BFS //We will keep track of all the land cells in a queue //We will iterate over the whole grid and if we encounter a water cell, we will check it's distance from all it's adjacent land cells //We will keep track of the max distance and return it at the end int maxDistance = -1; int n = grid.length; int m = grid[0].length; Queuequeue = new LinkedList<>(); for(int i=0; i = 0 && newR < n && newC >= 0 && newC < m && grid[newR][newC] == 0){ grid[newR][newC] = grid[r][c] + 1; queue.add(new int[]{newR, newC}); } } } } for(int i=0; i 1){ maxDistance = Math.max(maxDistance, grid[i][j] - 1); } } } return maxDistance; } }
from collections import deque class Solution: def maxDistance(self, grid: List[List[int]]) -> int: # BFS # initialize a queue and add all the land cells to it # iterate over the queue and for each land cell, check its neighbors # if any of the neighbors is water, add it to the queue and update its distance # return the maximum distance # corner case if not grid or not grid[0]: return -1 # initialize a queue and add all the land cells to it queue = deque() m = len(grid) n = len(grid[0]) for i in range(m): for j in range(n): if grid[i][j] == 1: queue.append((i, j)) # iterate over the queue and for each land cell, check its neighbors # if any of the neighbors is water, add it to the queue and update its distance # return the maximum distance max_dist = 0 while queue: i, j = queue.popleft() for x, y in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]: if 0 <= x < m and 0 <= y < n and grid[x][y] == 0: grid[x][y] = grid[i][j] + 1 max_dist = max(max_dist, grid[x][y]) queue.append((x, y)) return -1 if max_dist == 0 else max_dist - 1
var asFarFromLandAsPossible = function(grid) { // create a queue for BFS let queue = []; // create a visited matrix let visited = []; for (let i = 0; i < grid.length; i++) { visited.push([]); for (let j = 0; j < grid[0].length; j++) { visited[i].push(false); } } // get all the land cells and push them into the queue for (let i = 0; i < grid.length; i++) { for (let j = 0; j < grid[0].length; j++) { if (grid[i][j] === 1) { queue.push([i, j]); visited[i][j] = true; } } } // BFS let level = 0; let curr; while (queue.length > 0) { let size = queue.length; for (let i = 0; i < size; i++) { curr = queue.shift(); let currX = curr[0]; let currY = curr[1]; // check all 4 directions if (currX > 0 && visited[currX - 1][currY] === false) { queue.push([currX - 1, currY]); visited[currX - 1][currY] = true; } if (currX < grid.length - 1 && visited[currX + 1][currY] === false) { queue.push([currX + 1, currY]); visited[currX + 1][currY] = true; } if (currY > 0 && visited[currX][currY - 1] === false) { queue.push([currX, currY - 1]); visited[currX][currY - 1] = true; } if (currY < grid[0].length - 1 && visited[currX][currY + 1] === false) { queue.push([currX, currY + 1]); visited[currX][currY + 1] = true; } } level++; } return level - 1; };
The problem is as follows: Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water. class Solution { public: int maxDistance(vector>& grid) { int n = grid.size(), m = grid[0].size(); int ans = -1; queue > q; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { if(grid[i][j] == 1) { q.push({i, j}); } } } vector dx = {0, 0, 1, -1}; vector dy = {1, -1, 0, 0}; while(!q.empty()) { int size = q.size(); while(size--) { auto [x, y] = q.front(); q.pop(); for(int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if(nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == 0) { grid[nx][ny] = 1; q.push({nx, ny}); } } } ans++; } return ans == 0 ? -1 : ans - 1; } };
using System; class GFG { // Function to find the maximum // distance from any cell static int findMaxDistance(int[,] mat, int n, int m) { // To store maximum distance // from a land cell int result = -1; // To store land cells // in a queue QueueQ = new Queue (); // To store visited cells bool[,] visited = new bool[n, m]; // Loop over each cell for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { // If current cell is a water // cell, continue if (mat[i, j] == 0 || visited[i, j]) continue; // Add current cell to // the queue Q.Enqueue(new Pair(i, j)); // Distance of current cell // from the starting cell int dist = 0; // Do BFS starting from // current cell while (Q.Count != 0) { // Remove front item // from the queue Pair p = Q.Dequeue(); // Get i and j coordinates // of the current cell int x = p.x; int y = p.y; // If this is the starting // cell, continue if (x == i && y == j) continue; // If this has already been // visited, continue if (visited[x, y]) continue; // Mark this cell as visited visited[x, y] = true; // Update result result = Math.Max(result, dist); // Loop over all 8 possible // moves from current cell for (int row = x - 1; row <= x + 1; row++) { for (int col = y - 1; col <= y + 1; col++) { // If row number and column // number are valid and // current cell is not a // water cell and not // visited yet if (isValid(mat, row, col, n, m) && mat[row, col] == 1 && !visited[row, col]) { // enqueue newly found // water cell Q.Enqueue(new Pair(row, col)); // Increment distance // by 1 dist++; } } } } } } return result; } // Utility method to check if given // row and column are valid or not static bool isValid(int[,] mat, int row, int col, int n, int m) { if (row >= 0 && row < n && col >= 0 && col < m) return true; return false; } // Driver code public static void Main() { int n = 5, m = 5; int[,] mat = {{ 1, 0, 1, 0, 1 }, { 0, 1, 0, 0, 0 }, { 0, 0, 1, 0, 0 }, { 1, 0, 0, 0, 1 }, { 0, 0, 1, 0, 0 }}; Console.Write("Maximum distance " + "from a land cell is " + findMaxDistance(mat, n, m)); } } // Class to store row and column // of a cell class Pair { public int x, y; public Pair(int x, int y) { this.x = x; this.y = y; } }