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;
        
        Queue queue = 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 
    Queue Q = 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; 
    } 
}