As Far from Land as Possible

🎯

As Far from Land as Possible

mediumGRAPHGoogleAmazonFacebook

Imagine you are stranded on an island represented as a grid, and you want to find the spot in the ocean that is farthest from any land to build a safe refuge.

💡 This problem involves searching a grid to find the maximum distance from land cells to water cells. Beginners often struggle because they try to compute distances from each water cell individually, which is inefficient. Understanding multi-source BFS helps solve it optimally.

📋

Problem Statement

Given an n x n grid containing only 0s (water) and 1s (land), find a water cell such that its distance to the nearest land cell is maximized, and return this distance. Distance is measured in terms of Manhattan distance (up, down, left, right moves). If no water cell or no land cell exists, return -1.

1 ≤ n ≤ 100grid[i][j] is either 0 or 1

💡

Example

Input"[[1,0,1],[0,0,0],[1,0,1]]"

Output2

The water cell at the center (1,1) is 2 steps away from the nearest land cell.

Input"[[1,0,0],[0,0,0],[0,0,0]]"

Output4

The water cell at bottom-right corner is 4 steps away from the nearest land cell.

• Grid with all land cells → output -1
• Grid with all water cells → output -1
• Grid with only one land cell → maximum distance from that cell
• Grid with land cells only on edges → maximum distance inside grid

⚠️

Common Mistakes

Not handling edge cases with all land or all water

Returns incorrect distance or crashes

✅ Check if all cells are land or water and return -1 accordingly

Using DFS instead of BFS for shortest distance

Incorrect distances because DFS does not guarantee shortest path

✅ Use BFS to ensure shortest distance in unweighted grid

Not marking visited cells, causing infinite loops

Program hangs or runs very slowly

✅ Maintain a visited array or mark cells when enqueued

Updating distance incorrectly or forgetting to increment

Distance values are wrong, leading to wrong answer

✅ Update distance as current distance + 1 when visiting neighbors

Using nested loops to compute distances for each water cell (brute force) in large grids

Time limit exceeded in interviews

✅ Use multi-source BFS to optimize

🧠

Brute Force (Distance Calculation from Each Water Cell)

💡 This approach exists to build intuition by directly computing distances from every water cell to all land cells, showing why a naive solution is inefficient and motivating BFS.

Intuition

For each water cell, calculate the Manhattan distance to every land cell and keep track of the minimum distance. The answer is the maximum of these minimum distances.

Algorithm

1. Identify all land cells in the grid.
2. For each water cell, compute the Manhattan distance to every land cell.
3. Record the minimum distance for each water cell.
4. Return the maximum of these minimum distances, or -1 if no water or land exists.

💡 This algorithm is easy to understand but involves nested loops that quickly become expensive as grid size grows.

</>

Code

from typing import List

def maxDistance(grid: List[List[int]]) -> int:
    n = len(grid)
    land_positions = [(r, c) for r in range(n) for c in range(n) if grid[r][c] == 1]
    if not land_positions or len(land_positions) == n * n:
        return -1
    max_dist = -1
    for r in range(n):
        for c in range(n):
            if grid[r][c] == 0:
                min_dist = float('inf')
                for lr, lc in land_positions:
                    dist = abs(r - lr) + abs(c - lc)
                    if dist < min_dist:
                        min_dist = dist
                if min_dist > max_dist:
                    max_dist = min_dist
    return max_dist

# Driver code
if __name__ == '__main__':
    grid = [[1,0,1],[0,0,0],[1,0,1]]
    print(maxDistance(grid))  # Expected output: 2

Line Notes

land_positions = [(r, c) for r in range(n) for c in range(n) if grid[r][c] == 1]Collect all land cells to avoid repeated scanning inside nested loops

if not land_positions or len(land_positions) == n * n:Handle edge cases where no water or no land exists

for r in range(n):Iterate over all rows to check each cell

for c in range(n):Iterate over all columns to check each cell

if grid[r][c] == 0:Only compute distances for water cells

for lr, lc in land_positions:Check distance to every land cell for current water cell

dist = abs(r - lr) + abs(c - lc)Calculate Manhattan distance

if min_dist > max_dist:Update maximum minimum distance found so far

import java.util.*;

public class Solution {
    public static int maxDistance(int[][] grid) {
        int n = grid.length;
        List<int[]> landPositions = new ArrayList<>();
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == 1) {
                    landPositions.add(new int[]{r, c});
                }
            }
        }
        if (landPositions.isEmpty() || landPositions.size() == n * n) return -1;
        int maxDist = -1;
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == 0) {
                    int minDist = Integer.MAX_VALUE;
                    for (int[] land : landPositions) {
                        int dist = Math.abs(r - land[0]) + Math.abs(c - land[1]);
                        if (dist < minDist) minDist = dist;
                    }
                    if (minDist > maxDist) maxDist = minDist;
                }
            }
        }
        return maxDist;
    }

    public static void main(String[] args) {
        int[][] grid = {{1,0,1},{0,0,0},{1,0,1}};
        System.out.println(maxDistance(grid)); // Expected output: 2
    }
}

Line Notes

List<int[]> landPositions = new ArrayList<>();Store all land cells to avoid repeated scanning

if (landPositions.isEmpty() || landPositions.size() == n * n) return -1;Check for edge cases with no water or no land

for (int r = 0; r < n; r++) {Loop over rows to examine each cell

if (grid[r][c] == 0) {Process only water cells

for (int[] land : landPositions) {Calculate distance to every land cell

int dist = Math.abs(r - land[0]) + Math.abs(c - land[1]);Compute Manhattan distance

if (minDist > maxDist) maxDist = minDist;Update maximum minimum distance

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>
using namespace std;

int maxDistance(vector<vector<int>>& grid) {
    int n = grid.size();
    vector<pair<int,int>> landPositions;
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == 1) {
                landPositions.push_back({r, c});
            }
        }
    }
    if (landPositions.empty() || landPositions.size() == n * n) return -1;
    int maxDist = -1;
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == 0) {
                int minDist = INT_MAX;
                for (auto& land : landPositions) {
                    int dist = abs(r - land.first) + abs(c - land.second);
                    if (dist < minDist) minDist = dist;
                }
                if (minDist > maxDist) maxDist = minDist;
            }
        }
    }
    return maxDist;
}

int main() {
    vector<vector<int>> grid = {{1,0,1},{0,0,0},{1,0,1}};
    cout << maxDistance(grid) << endl; // Expected output: 2
    return 0;
}

Line Notes

vector<pair<int,int>> landPositions;Collect all land cells for distance calculations

if (landPositions.empty() || landPositions.size() == n * n) return -1;Handle edge cases with no water or no land

for (int r = 0; r < n; r++) {Iterate over rows to check each cell

if (grid[r][c] == 0) {Only compute distances for water cells

for (auto& land : landPositions) {Calculate distance to every land cell

int dist = abs(r - land.first) + abs(c - land.second);Compute Manhattan distance

if (minDist > maxDist) maxDist = minDist;Update maximum minimum distance

function maxDistance(grid) {
    const n = grid.length;
    const landPositions = [];
    for (let r = 0; r < n; r++) {
        for (let c = 0; c < n; c++) {
            if (grid[r][c] === 1) {
                landPositions.push([r, c]);
            }
        }
    }
    if (landPositions.length === 0 || landPositions.length === n * n) return -1;
    let maxDist = -1;
    for (let r = 0; r < n; r++) {
        for (let c = 0; c < n; c++) {
            if (grid[r][c] === 0) {
                let minDist = Infinity;
                for (const [lr, lc] of landPositions) {
                    const dist = Math.abs(r - lr) + Math.abs(c - lc);
                    if (dist < minDist) minDist = dist;
                }
                if (minDist > maxDist) maxDist = minDist;
            }
        }
    }
    return maxDist;
}

// Test
console.log(maxDistance([[1,0,1],[0,0,0],[1,0,1]])); // Expected output: 2

Line Notes

const landPositions = [];Store all land cells to avoid repeated scanning

if (landPositions.length === 0 || landPositions.length === n * n) return -1;Check for edge cases with no water or no land

for (let r = 0; r < n; r++) {Loop over rows to examine each cell

if (grid[r][c] === 0) {Process only water cells

for (const [lr, lc] of landPositions) {Calculate distance to every land cell

const dist = Math.abs(r - lr) + Math.abs(c - lc);Compute Manhattan distance

if (minDist > maxDist) maxDist = minDist;Update maximum minimum distance

⏱

Complexity

TimeO(n^4)

SpaceO(n^2)

For each water cell (up to n^2), we compute distance to all land cells (up to n^2), resulting in O(n^4) time. Space is O(n^2) to store land positions.

💡 For n=10, this means 10,000 water cells times 100 land cells = 1,000,000 operations, which is slow but manageable. For n=100, it becomes 100 million operations, which is too slow.

Interview Verdict: TLE

This approach is too slow for large inputs, so it is mainly useful to understand the problem and motivate better solutions.

🧠

Better Approach: Multi-Source BFS from All Land Cells

💡 This approach improves efficiency by starting BFS simultaneously from all land cells, spreading outwards to find the farthest water cell, avoiding repeated distance calculations.

Intuition

Treat all land cells as sources and perform BFS to expand into water cells layer by layer. The last water cell reached in BFS has the maximum distance from land.

Algorithm

1. Initialize a queue with all land cells and mark them as visited.
2. Perform BFS, expanding to adjacent water cells and marking their distance.
3. Track the distance level as BFS progresses.
4. Return the maximum distance found, or -1 if no water cell exists.

💡 This algorithm uses BFS layers to measure distance from land, which is more efficient than brute force nested loops.

</>

Code

from collections import deque
from typing import List

def maxDistance(grid: List[List[int]]) -> int:
    n = len(grid)
    queue = deque()
    visited = [[False]*n for _ in range(n)]

    # Add all land cells to queue
    for r in range(n):
        for c in range(n):
            if grid[r][c] == 1:
                queue.append((r, c))
                visited[r][c] = True

    if len(queue) == 0 or len(queue) == n * n:
        return -1

    directions = [(1,0), (-1,0), (0,1), (0,-1)]
    distance = -1

    while queue:
        distance += 1
        for _ in range(len(queue)):
            r, c = queue.popleft()
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and not visited[nr][nc] and grid[nr][nc] == 0:
                    visited[nr][nc] = True
                    queue.append((nr, nc))

    return distance

# Driver code
if __name__ == '__main__':
    grid = [[1,0,1],[0,0,0],[1,0,1]]
    print(maxDistance(grid))  # Expected output: 2

Line Notes

queue = deque()Initialize queue for BFS traversal

visited = [[False]*n for _ in range(n)]Track visited cells to avoid revisiting

for r in range(n):Scan grid to enqueue all land cells as BFS sources

if grid[r][c] == 1:Land cells are starting points for BFS

if len(queue) == 0 or len(queue) == n * n:Handle edge cases with no water or no land

while queue:Process BFS level by level

distance += 1Increment distance at each BFS layer

for _ in range(len(queue))Process all nodes at current BFS level

if 0 <= nr < n and 0 <= nc < n and not visited[nr][nc] and grid[nr][nc] == 0:Add unvisited water neighbors to queue

import java.util.*;

public class Solution {
    public static int maxDistance(int[][] grid) {
        int n = grid.length;
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[n][n];

        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == 1) {
                    queue.offer(new int[]{r, c});
                    visited[r][c] = true;
                }
            }
        }

        if (queue.isEmpty() || queue.size() == n * n) return -1;

        int[][] directions = {{1,0}, {-1,0}, {0,1}, {0,-1}};
        int distance = -1;

        while (!queue.isEmpty()) {
            int size = queue.size();
            distance++;
            for (int i = 0; i < size; i++) {
                int[] cell = queue.poll();
                int r = cell[0], c = cell[1];
                for (int[] d : directions) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc] && grid[nr][nc] == 0) {
                        visited[nr][nc] = true;
                        queue.offer(new int[]{nr, nc});
                    }
                }
            }
        }

        return distance;
    }

    public static void main(String[] args) {
        int[][] grid = {{1,0,1},{0,0,0},{1,0,1}};
        System.out.println(maxDistance(grid)); // Expected output: 2
    }
}

Line Notes

Queue<int[]> queue = new LinkedList<>();Initialize BFS queue

boolean[][] visited = new boolean[n][n];Track visited cells to prevent revisits

if (grid[r][c] == 1) {Enqueue all land cells as BFS sources

if (queue.isEmpty() || queue.size() == n * n) return -1;Handle edge cases with no water or no land

while (!queue.isEmpty()) {Process BFS layers until no more water cells

distance++;Increment distance at each BFS level

for (int i = 0; i < size; i++) {Process all nodes at current BFS level

if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc] && grid[nr][nc] == 0)Add valid unvisited water neighbors

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int maxDistance(vector<vector<int>>& grid) {
    int n = grid.size();
    queue<pair<int,int>> q;
    vector<vector<bool>> visited(n, vector<bool>(n, false));

    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == 1) {
                q.push({r, c});
                visited[r][c] = true;
            }
        }
    }

    if (q.empty() || q.size() == n * n) return -1;

    int distance = -1;
    int directions[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};

    while (!q.empty()) {
        int size = q.size();
        distance++;
        for (int i = 0; i < size; i++) {
            auto [r, c] = q.front(); q.pop();
            for (auto& d : directions) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc] && grid[nr][nc] == 0) {
                    visited[nr][nc] = true;
                    q.push({nr, nc});
                }
            }
        }
    }

    return distance;
}

int main() {
    vector<vector<int>> grid = {{1,0,1},{0,0,0},{1,0,1}};
    cout << maxDistance(grid) << endl; // Expected output: 2
    return 0;
}

Line Notes

queue<pair<int,int>> q;Initialize BFS queue for grid cells

vector<vector<bool>> visited(n, vector<bool>(n, false));Track visited cells to avoid revisiting

if (grid[r][c] == 1) {Enqueue all land cells as BFS starting points

if (q.empty() || q.size() == n * n) return -1;Handle edge cases with no water or no land

while (!q.empty()) {Process BFS layers until no more water cells

distance++;Increment distance at each BFS level

for (int i = 0; i < size; i++) {Process all nodes at current BFS level

if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc] && grid[nr][nc] == 0)Add valid unvisited water neighbors

function maxDistance(grid) {
    const n = grid.length;
    const queue = [];
    const visited = Array.from({length: n}, () => Array(n).fill(false));

    for (let r = 0; r < n; r++) {
        for (let c = 0; c < n; c++) {
            if (grid[r][c] === 1) {
                queue.push([r, c]);
                visited[r][c] = true;
            }
        }
    }

    if (queue.length === 0 || queue.length === n * n) return -1;

    const directions = [[1,0], [-1,0], [0,1], [0,-1]];
    let distance = -1;

    while (queue.length > 0) {
        let size = queue.length;
        distance++;
        for (let i = 0; i < size; i++) {
            const [r, c] = queue.shift();
            for (const [dr, dc] of directions) {
                const nr = r + dr, nc = c + dc;
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc] && grid[nr][nc] === 0) {
                    visited[nr][nc] = true;
                    queue.push([nr, nc]);
                }
            }
        }
    }

    return distance;
}

// Test
console.log(maxDistance([[1,0,1],[0,0,0],[1,0,1]])); // Expected output: 2

Line Notes

const queue = [];Initialize BFS queue

const visited = Array.from({length: n}, () => Array(n).fill(false));Track visited cells to avoid revisiting

if (grid[r][c] === 1) {Enqueue all land cells as BFS sources

if (queue.length === 0 || queue.length === n * n) return -1;Handle edge cases with no water or no land

while (queue.length > 0) {Process BFS layers until no more water cells

distance++;Increment distance at each BFS level

for (let i = 0; i < size; i++) {Process all nodes at current BFS level

if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc] && grid[nr][nc] === 0)Add valid unvisited water neighbors

⏱

Complexity

TimeO(n^2)

SpaceO(n^2)

Each cell is visited at most once in BFS, so time is O(n^2). Space is O(n^2) for the queue and visited array.

💡 For n=100, this means at most 10,000 operations, which is efficient and suitable for interviews.

Interview Verdict: Accepted

This is the optimal and accepted approach, demonstrating mastery of BFS and multi-source traversal.

🧠

Alternative Approach: BFS with Distance Matrix

💡 This approach explicitly maintains a distance matrix to track the shortest distance from land to each water cell, reinforcing BFS layer concepts.

Intuition

Initialize distances for land cells as 0 and water cells as -1. BFS updates distances for neighbors, ensuring shortest distance propagation.

Algorithm

1. Create a distance matrix initialized with -1 for water and 0 for land.
2. Enqueue all land cells.
3. Perform BFS, updating distance for each water neighbor as current cell distance + 1.
4. Return the maximum distance found in the distance matrix.

💡 This approach makes distance updates explicit, helping beginners visualize BFS progression.

</>

Code

from collections import deque
from typing import List

def maxDistance(grid: List[List[int]]) -> int:
    n = len(grid)
    dist = [[-1]*n for _ in range(n)]
    queue = deque()

    for r in range(n):
        for c in range(n):
            if grid[r][c] == 1:
                dist[r][c] = 0
                queue.append((r, c))

    if len(queue) == 0 or len(queue) == n * n:
        return -1

    directions = [(1,0), (-1,0), (0,1), (0,-1)]
    max_dist = -1

    while queue:
        r, c = queue.popleft()
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1
                max_dist = max(max_dist, dist[nr][nc])
                queue.append((nr, nc))

    return max_dist

# Driver code
if __name__ == '__main__':
    grid = [[1,0,1],[0,0,0],[1,0,1]]
    print(maxDistance(grid))  # Expected output: 2

Line Notes

dist = [[-1]*n for _ in range(n)]Initialize distance matrix with -1 for unvisited water cells

if grid[r][c] == 1:Set distance 0 for land cells and enqueue them

if len(queue) == 0 or len(queue) == n * n:Handle edge cases with no water or no land

while queue:Process BFS until all reachable water cells are visited

if dist[nr][nc] == -1:Only update distance for unvisited water cells

dist[nr][nc] = dist[r][c] + 1Update distance as one more than current cell

max_dist = max(max_dist, dist[nr][nc])Track maximum distance found

import java.util.*;

public class Solution {
    public static int maxDistance(int[][] grid) {
        int n = grid.length;
        int[][] dist = new int[n][n];
        for (int[] row : dist) Arrays.fill(row, -1);
        Queue<int[]> queue = new LinkedList<>();

        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == 1) {
                    dist[r][c] = 0;
                    queue.offer(new int[]{r, c});
                }
            }
        }

        if (queue.isEmpty() || queue.size() == n * n) return -1;

        int[][] directions = {{1,0}, {-1,0}, {0,1}, {0,-1}};
        int maxDist = -1;

        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int r = cell[0], c = cell[1];
            for (int[] d : directions) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && dist[nr][nc] == -1) {
                    dist[nr][nc] = dist[r][c] + 1;
                    maxDist = Math.max(maxDist, dist[nr][nc]);
                    queue.offer(new int[]{nr, nc});
                }
            }
        }

        return maxDist;
    }

    public static void main(String[] args) {
        int[][] grid = {{1,0,1},{0,0,0},{1,0,1}};
        System.out.println(maxDistance(grid)); // Expected output: 2
    }
}

Line Notes

int[][] dist = new int[n][n];Distance matrix initialized to -1 for water cells

if (grid[r][c] == 1) {Set distance 0 for land cells and enqueue

if (queue.isEmpty() || queue.size() == n * n) return -1;Handle edge cases

while (!queue.isEmpty()) {BFS traversal to update distances

if (dist[nr][nc] == -1) {Update only unvisited water cells

dist[nr][nc] = dist[r][c] + 1;Distance is one more than current cell

maxDist = Math.max(maxDist, dist[nr][nc]);Track maximum distance

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int maxDistance(vector<vector<int>>& grid) {
    int n = grid.size();
    vector<vector<int>> dist(n, vector<int>(n, -1));
    queue<pair<int,int>> q;

    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == 1) {
                dist[r][c] = 0;
                q.push({r, c});
            }
        }
    }

    if (q.empty() || q.size() == n * n) return -1;

    int directions[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
    int maxDist = -1;

    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();
        for (auto& d : directions) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < n && nc >= 0 && nc < n && dist[nr][nc] == -1) {
                dist[nr][nc] = dist[r][c] + 1;
                maxDist = max(maxDist, dist[nr][nc]);
                q.push({nr, nc});
            }
        }
    }

    return maxDist;
}

int main() {
    vector<vector<int>> grid = {{1,0,1},{0,0,0},{1,0,1}};
    cout << maxDistance(grid) << endl; // Expected output: 2
    return 0;
}

Line Notes

vector<vector<int>> dist(n, vector<int>(n, -1));Initialize distance matrix with -1 for water

if (grid[r][c] == 1) {Set distance 0 for land and enqueue

if (q.empty() || q.size() == n * n) return -1;Handle edge cases

while (!q.empty()) {BFS traversal to update distances

if (dist[nr][nc] == -1) {Update only unvisited water cells

dist[nr][nc] = dist[r][c] + 1;Distance is one more than current cell

maxDist = max(maxDist, dist[nr][nc]);Track maximum distance

function maxDistance(grid) {
    const n = grid.length;
    const dist = Array.from({length: n}, () => Array(n).fill(-1));
    const queue = [];

    for (let r = 0; r < n; r++) {
        for (let c = 0; c < n; c++) {
            if (grid[r][c] === 1) {
                dist[r][c] = 0;
                queue.push([r, c]);
            }
        }
    }

    if (queue.length === 0 || queue.length === n * n) return -1;

    const directions = [[1,0], [-1,0], [0,1], [0,-1]];
    let maxDist = -1;

    while (queue.length > 0) {
        const [r, c] = queue.shift();
        for (const [dr, dc] of directions) {
            const nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < n && nc >= 0 && nc < n && dist[nr][nc] === -1) {
                dist[nr][nc] = dist[r][c] + 1;
                maxDist = Math.max(maxDist, dist[nr][nc]);
                queue.push([nr, nc]);
            }
        }
    }

    return maxDist;
}

// Test
console.log(maxDistance([[1,0,1],[0,0,0],[1,0,1]])); // Expected output: 2

Line Notes

const dist = Array.from({length: n}, () => Array(n).fill(-1));Initialize distance matrix with -1 for water

if (grid[r][c] === 1) {Set distance 0 for land and enqueue

if (queue.length === 0 || queue.length === n * n) return -1;Handle edge cases

while (queue.length > 0) {BFS traversal to update distances

if (dist[nr][nc] === -1) {Update only unvisited water cells

dist[nr][nc] = dist[r][c] + 1;Distance is one more than current cell

maxDist = Math.max(maxDist, dist[nr][nc]);Track maximum distance

⏱

Complexity

TimeO(n^2)

SpaceO(n^2)

Each cell is visited once in BFS, so time is O(n^2). Space is O(n^2) for distance matrix and queue.

💡 This approach is similar to the previous BFS but makes distance tracking explicit, which can help beginners understand BFS layers.

Interview Verdict: Accepted

This approach is also optimal and accepted, useful for clarity and teaching BFS distance propagation.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, always code the multi-source BFS approach (Approach 2 or 3) because it is efficient and clear. Mention brute force to show understanding but avoid coding it.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^4)	O(n^2)	No	N/A	Mention only - never code due to inefficiency
2. Multi-Source BFS (Visited Matrix)	O(n^2)	O(n^2)	No	Yes, can track path if needed	Code this approach for optimal solution
3. BFS with Distance Matrix	O(n^2)	O(n^2)	No	Yes, explicit distances help	Alternative to approach 2, good for clarity

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain the brute force approach to show understanding, followed by the optimal BFS solution. Practice coding and testing edge cases.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach and its inefficiency.Step 3: Introduce the multi-source BFS approach as an optimization.Step 4: Write clean, tested code for the BFS solution.Step 5: Discuss edge cases and test your code with them.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

The interviewer tests your understanding of BFS, ability to optimize brute force solutions, handle edge cases, and write clean code.

Common Follow-ups

• What if diagonal moves were allowed? → Modify BFS directions to include diagonals.
• How to find the actual cell with maximum distance? → Track coordinates during BFS.

💡 These follow-ups test your ability to adapt BFS and extend the solution beyond the basic problem.

🔍

Pattern Recognition

When to Use

1) Grid or matrix input with land and water cells; 2) Need to find shortest or maximum distance; 3) Movement allowed in four directions; 4) Multiple sources of BFS (all land cells).

Signature Phrases

'distance to nearest land''find water cell farthest from land''multi-source BFS''grid with 0s and 1s'

NOT This Pattern When

Problems involving weighted shortest paths or requiring DFS for cycle detection are different patterns.

Similar Problems

01 Matrix - BFS from multiple sources to find nearest zeroWalls and Gates - BFS to find shortest distance to gatesRotting Oranges - BFS spreading infection from multiple sources

Practice

1. Consider the following Python code implementing flood fill using DFS. Given the input image = [[1,1,1],[1,1,0],[1,0,1]], starting pixel (sr=1, sc=1), and newColor=2, what is the final image returned?

easy

A. [[1,1,1],[1,2,0],[1,0,1]]

B. [[2,2,2],[2,2,0],[2,0,2]]

C. [[2,2,2],[2,2,0],[2,0,1]]

D. [[2,2,2],[2,2,2],[2,2,2]]

Solution

1. Step 1: Trace dfs starting at (1,1) with original color=1

   The pixel at (1,1) is recolored to 2. Its neighbors with color 1 are (0,1), (2,1) is 0 so skipped, (1,0), and (1,2) is 0 skipped.

2. Step 2: Recursively recolor connected pixels with color 1

   All connected pixels with color 1 reachable from (1,1) are recolored to 2, resulting in [[2,2,2],[2,2,0],[2,0,1]]. The pixel at (2,2) remains 1 as it is not connected 4-directionally.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Only connected pixels with original color changed [OK]

Hint: Trace DFS calls carefully to find connected pixels [OK]

Common Mistakes:

• Changing pixels diagonally connected
• Forgetting to check boundaries

2. You are given an undirected graph and need to determine if its vertices can be divided into two groups such that no edge connects vertices within the same group. Which algorithmic approach guarantees an efficient and correct solution for this problem?

easy

A. Greedy algorithm that assigns groups based on vertex degree

B. Dynamic Programming on subsets of vertices to find valid partitions

C. Depth-First Search (DFS) to find cycles and count their lengths

D. Breadth-First Search (BFS) coloring to assign two colors and check for conflicts

Solution

1. Step 1: Understand the problem as a 2-coloring challenge

   The problem requires checking if the graph is bipartite, which means it can be colored using two colors such that no adjacent vertices share the same color.

2. Step 2: Identify BFS coloring as the optimal approach

   BFS coloring systematically assigns colors level by level and detects conflicts efficiently, guaranteeing correctness and linear time complexity.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   BFS coloring is the standard method for bipartite checking [OK]

Hint: BFS coloring detects bipartite conflicts efficiently [OK]

Common Mistakes:

• Assuming greedy degree-based grouping works
• Confusing cycle detection with bipartite check

3. You are given a directed graph with weighted edges representing travel times between nodes. Starting from a given node, you want to find the minimum time it takes for a signal to reach all other nodes. Which algorithmic approach guarantees finding the shortest travel times in this scenario?

easy

A. Use Dijkstra's algorithm with a priority queue to greedily select the next closest node.

B. Use a greedy algorithm that always picks the edge with the smallest weight regardless of path.

C. Use a simple Breadth-First Search (BFS) assuming all edges have equal weight.

D. Use a Depth-First Search (DFS) with path relaxation to explore all paths.

Solution

1. Step 1: Understand the problem requires shortest paths with weighted edges

   BFS assumes equal edge weights and cannot handle varying weights correctly, so it fails here.

2. Step 2: Identify that Dijkstra's algorithm uses a priority queue to always pick the next closest node, guaranteeing optimal shortest paths in graphs with non-negative weights

   DFS with path relaxation is inefficient and does not guarantee optimality without pruning, and greedy edge picking ignores path costs.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Dijkstra handles weighted shortest paths optimally [OK]

Hint: Dijkstra handles weighted shortest paths optimally [OK]

Common Mistakes:

• Assuming BFS works for weighted graphs
• Thinking DFS with relaxation is efficient
• Believing greedy edge picking always works

4. What is the worst-case time complexity of the DFS-based solution for the Rotting Oranges problem on an m x n grid, considering pruning and recursive calls?

medium

A. O(m * n * 4) due to each cell visited once with up to 4 neighbors

B. O(m * n * m * n) because each cell can be revisited multiple times

C. O(m * n) ignoring recursion stack and repeated visits

D. O(m * n * T) where T is the number of minutes until no change

Solution

1. Step 1: Identify number of cells and neighbors

   Grid has m*n cells; each cell has up to 4 neighbors to explore.

2. Step 2: Consider pruning and repeated visits

   Pruning ensures each cell is visited at most once per time update, bounding calls to O(m*n*4).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DFS with pruning limits repeated visits, so complexity is O(m*n*4) [OK]

Hint: Pruning limits DFS calls to constant neighbors per cell [OK]

Common Mistakes:

• Assuming exponential revisits
• Confusing time steps with grid size
• Ignoring recursion stack space

5. Suppose the problem is modified so that you can revisit cells multiple times (cycles allowed) and want to find the minimum effort path. Which approach correctly adapts to this change?

hard

A. Use the same Dijkstra's variant without changes; revisiting is naturally handled

B. Use binary search over effort and BFS to check feasibility without distance updates

C. Use DFS with pruning to explore all paths allowing revisits

D. Modify Dijkstra to allow updating distances even if a node was visited before, to handle cycles

Solution

1. Step 1: Understand revisiting impact

   Allowing revisits means shortest path distances can improve after initial visit, so standard Dijkstra's visited set is insufficient.

2. Step 2: Adapt algorithm

   Dijkstra must allow updating distances and pushing nodes multiple times to handle cycles correctly.

3. Step 3: Evaluate other options

   DFS is inefficient; binary search + BFS may work but requires careful feasibility checks; naive Dijkstra fails.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Allowing distance updates handles cycles correctly [OK]

Hint: Cycles require relaxing visited constraints in Dijkstra [OK]

Common Mistakes:

• Assuming no changes needed for revisits
• Using DFS without pruning causes TLE
• Binary search feasibility fails without updates