As Far from Land as Possible solution and explanation
Google
9 more videos on this problem
As Far from Land as Possible - Leetcode 1162 - PythonNeetCodeIO · 12:16 · 13K views
1162. As Far from Land as PossibleKelvin Chandra · 6:18 · 5K views
G-08 BFS Problem Type-3 II Multi-Source BFS || As Far from Land as Possible || Leetcode - 1162Aryan Mittal · 13:35 · 3K views
Leetcode 1162 As Far from Land as Possible - Java BFS SolutionAlgorithmicIQ · 16:40 · 1K views
Leetcode 1162 As Far from Land as Possible | SDE Sheet belowCoding Decoded · 13:10 · 1K views
1162. As Far from Land as Possible | LeetCode MediumDeep Tech · 22:54 · 1K views
As Far from Land as Possible - Leetcode 1162 - PythonTechError · 13:04 · 563 views
1162. As Far from Land as Possible (Leetcode Medium)Programming Live with Larry · 10:13 · 394 views
Leetcode 1162. As Far from Land as Possible - multi-source BFSCode-Yao · 10:08 · 366 views
Daily Leetcode #1046: Feb 10, 2023 - 1162. As Far from Land as PossibleProgramming Live with Larry · 2:25 · 308 views
The problem
Given an n x n grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized, and return the distance. If no land or water exists in the grid, return -1.
The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1) is |x0 - x1| + |y0 - y1|.
Example 1:
Input: grid = [[1,0,1],[0,0,0],[1,0,1]] Output: 2 Explanation: The cell (1, 1) is as far as possible from all the land with distance 2.
Example 2:
Input: grid = [[1,0,0],[0,0,0],[0,0,0]] Output: 4 Explanation: The cell (2, 2) is as far as possible from all the land with distance 4.
Constraints:
n == grid.lengthn == grid[i].length1 <= n <= 100grid[i][j]is0or1
Approach overview
Problem Overview: You get an n x n grid where 1 represents land and 0 represents water. The goal is to find the water cell whose Manhattan distance to the nearest land cell is maximized. If the grid contains only land or only water, return -1.
Approach 1: Brute Force Distance Search (O(n^4) time, O(1) space)
Iterate through every water cell and compute its distance to every land cell. Track the minimum distance to land for that water cell, then update the global maximum. The Manhattan distance between two cells (r1,c1) and (r2,c2) is |r1-r2| + |c1-c2|. This approach performs two nested loops for selecting a water cell and two more loops for scanning all land cells, resulting in O(n^4) time. The implementation is straightforward but extremely slow for larger grids. It mainly helps demonstrate the core idea: each water cell cares about the closest land.
Approach 2: Multi-Source Breadth-First Search (BFS) (O(n^2) time, O(n^2) space)
The optimal solution treats all land cells as starting points of a Breadth-First Search. Insert every land cell into a queue and expand outward simultaneously. Each BFS layer represents moving one step farther away from land. As the search spreads through neighboring cells (up, down, left, right), it converts water cells into visited nodes and pushes them into the queue. The last layer processed corresponds to the water cells farthest from any land.
This works because BFS always processes nodes in increasing distance order. Starting from all land cells guarantees that the first time a water cell is reached is the shortest distance to land. Track the number of BFS levels processed until the queue is empty. That level count becomes the answer.
The grid itself can act as the visited structure by marking visited water cells as land or another value. Each cell is processed at most once, giving O(n^2) time complexity. The queue may store up to all cells in the grid, so space complexity is also O(n^2). This pattern appears frequently in matrix problems where distances expand from multiple sources.
Approach 3: Dynamic Programming Distance Propagation (O(n^2) time, O(n^2) space)
A distance transform technique can also solve the problem using dynamic programming. Initialize distances as 0 for land and a large value for water. Perform two passes across the grid: top-left to bottom-right and bottom-right to top-left. Each pass relaxes distances using neighbors. This gradually propagates the shortest distance to land across the grid. After computing distances, scan water cells and return the maximum value. The approach is efficient but less intuitive in interviews compared to BFS.
Recommended for interviews: Multi-source BFS is the expected solution. It directly models distance expansion from all land cells and runs in optimal O(n^2) time. Interviewers usually want to see recognition of the multi-source BFS pattern in array grid problems. Showing the brute-force idea first demonstrates understanding of the distance definition, while the BFS optimization demonstrates algorithmic maturity.
Approach 1: Breadth-First Search (BFS) Approach
This approach uses BFS starting from all land cells simultaneously. We can think of the lands spreading out like waves in unison into the water cells, each wave representing a unit of distance. This helps us efficiently compute the farthest distance of a water cell from land.
from collections import deque
def maxDistance(grid):
n = len(grid)
queue = deque()
hasWater = False
for i in range(n):
for j in range(n):
if grid[i][j] == 1:
queue.append((i, j))
else:
hasWater = True
if len(queue) == 0 or not hasWater:
return -1
distance = -1
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while queue:
size = len(queue)
for _ in range(size):
x, y = queue.popleft()
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == 0:
grid[nx][ny] = 1
queue.append((nx, ny))
distance += 1
return distanceimport java.util.LinkedList;
import java.util.Queue;
public class Solution {
public int maxDistance(int[][] grid) {
int n = grid.length;
Queue<int[]> queue = new LinkedList<>();
boolean hasWater = false;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
queue.offer(new int[]{i, j});
} else {
hasWater = true;
}
}
}
if (queue.size() == n * n || !hasWater) return -1;
int distance = -1;
int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!queue.isEmpty()) {
int size = queue.size();
for (int k = 0; k < size; k++) {
int[] cell = queue.poll();
for (int[] direction : directions) {
int x = cell[0] + direction[0];
int y = cell[1] + direction[1];
if (x >= 0 && y >= 0 && x < n && y < n && grid[x][y] == 0) {
grid[x][y] = 1;
queue.offer(new int[]{x, y});
}
}
}
distance++;
}
return distance;
}
}#include <vector>
#include <queue>
#include <utility>
using namespace std;
int maxDistance(vector<vector<int>>& grid) {
int n = grid.size();
queue<pair<int, int>> q;
int directions[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
bool hasWater = false;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
q.push({i, j});
} else {
hasWater = true;
}
}
}
if (q.size() == n * n || !hasWater) return -1;
int distance = -1;
while (!q.empty()) {
int size = q.size();
while (size--) {
auto [x, y] = q.front();
q.pop();
for (auto& d : directions) {
int nx = x + d[0], ny = y + d[1];
if (nx >= 0 && ny >= 0 && nx < n && ny < n && grid[nx][ny] == 0) {
grid[nx][ny] = 1;
q.push({nx, ny});
}
}
}
distance++;
}
return distance;
}function maxDistance(grid) {
const n = grid.length;
const queue = [];
let hasWater = false;
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 1) {
queue.push([i, j]);
} else {
hasWater = true;
}
}
}
if (queue.length === 0 || !hasWater) return -1;
const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
let distance = -1;
while (queue.length > 0) {
const size = queue.length;
for (let k = 0; k < size; k++) {
const [x, y] = queue.shift();
for (const [dx, dy] of directions) {
const nx = x + dx, ny = y + dy;
if (nx >= 0 && ny >= 0 && nx < n && ny < n && grid[nx][ny] === 0) {
grid[nx][ny] = 1;
queue.push([nx, ny]);
}
}
}
distance++;
}
return distance;
}#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define MAXN 100
int maxDistance(int** grid, int gridSize, int* gridColSize) {
int n = gridSize;
int queue[MAXN * MAXN][2];
int front = 0, rear = 0;
int directions[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
bool hasWater = false;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
queue[rear][0] = i;
queue[rear][1] = j;
rear++;
} else {
hasWater = true;
}
}
}
if (rear == n * n || !hasWater) return -1;
int distance = -1;
while (front < rear) {
int size = rear - front;
while (size--) {
int x = queue[front][0];
int y = queue[front][1];
front++;
for (int d = 0; d < 4; d++) {
int nx = x + directions[d][0];
int ny = y + directions[d][1];
if (nx >= 0 && ny >= 0 && nx < n && ny < n && grid[nx][ny] == 0) {
grid[nx][ny] = 1;
queue[rear][0] = nx;
queue[rear][1] = ny;
rear++;
}
}
}
distance++;
}
return distance;
}using System;
using System.Collections.Generic;
public class Solution {
public int MaxDistance(int[][] grid) {
int n = grid.Length;
Queue<(int, int)> queue = new Queue<(int, int)>();
bool hasWater = false;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
queue.Enqueue((i, j));
} else {
hasWater = true;
}
}
}
if (queue.Count == n * n || !hasWater) return -1;
int distance = -1;
int[][] directions = { new int[]{1, 0}, new int[]{-1, 0}, new int[]{0, 1}, new int[]{0, -1} };
while (queue.Count > 0) {
int size = queue.Count;
for (int k = 0; k < size; k++) {
var (x, y) = queue.Dequeue();
foreach (var dir in directions) {
int nx = x + dir[0];
int ny = y + dir[1];
if (nx >= 0 && ny >= 0 && nx < n && ny < n && grid[nx][ny] == 0) {
grid[nx][ny] = 1;
queue.Enqueue((nx, ny));
}
}
}
distance++;
}
return distance;
}
}This Python solution uses a deque from the collections module to efficiently perform BFS. The grid's cells are converted to land as they are processed, leveraging BFS layers to determine the farthest water distance.
Time complexity is O(n2) and space complexity is O(n2) due to the queue storing each cell at most once.
Approach 2: BFS
We can add all land cells to the queue q. If the queue is empty, or the number of elements in the queue equals the number of cells in the grid, it means that the grid contains only land or ocean, so return -1.
Otherwise, we start BFS from the land cells. Define the initial step count ans=-1.
In each round of search, we spread all cells in the queue in four directions. If a cell is an ocean cell, we mark it as a land cell and add it to the queue. After a round of spreading, we increase the step count by 1. Repeat this process until the queue is empty.
Finally, we return the step count ans.
The time complexity is O(n^2), and the space complexity is O(n^2). Here, n is the side length of the grid.
function maxDistance(grid: number[][]): number {
const n = grid.length;
const q: [number, number][] = [];
for (let i = 0; i < n; ++i) {
for (let j = 0; j < n; ++j) {
if (grid[i][j] === 1) {
q.push([i, j]);
}
}
}
let ans = -1;
if (q.length === 0 || q.length === n * n) {
return ans;
}
const dirs: number[] = [-1, 0, 1, 0, -1];
while (q.length > 0) {
for (let m = q.length; m; --m) {
const [i, j] = q.shift()!;
for (let k = 0; k < 4; ++k) {
const x = i + dirs[k];
const y = j + dirs[k + 1];
if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y] === 0) {
grid[x][y] = 1;
q.push([x, y]);
}
}
}
++ans;
}
return ans;
}func maxDistance(grid [][]int) int {
n := len(grid)
q := [][2]int{}
for i, row := range grid {
for j, v := range row {
if v == 1 {
q = append(q, [2]int{i, j})
}
}
}
ans := -1
if len(q) == 0 || len(q) == n*n {
return ans
}
dirs := [5]int{-1, 0, 1, 0, -1}
for len(q) > 0 {
for i := len(q); i > 0; i-- {
p := q[0]
q = q[1:]
for k := 0; k < 4; k++ {
x, y := p[0]+dirs[k], p[1]+dirs[k+1]
if x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 0 {
grid[x][y] = 1
q = append(q, [2]int{x, y})
}
}
}
ans++
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) Approach | Time complexity is O(n2) and space complexity is O(n2) due to the queue storing each cell at most once. |
| BFS | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Distance Check | O(n^4) | O(1) | Understanding the distance definition or very small grids |
| Multi-Source BFS | O(n^2) | O(n^2) | Optimal solution for grid distance problems and interview settings |
| Dynamic Programming Distance Transform | O(n^2) | O(n^2) | When avoiding BFS queues or applying matrix DP distance propagation |
Frequently asked questions
Is As Far from Land as Possible easy or hard?
As Far from Land as Possible is rated Medium on LeetCode. The difficulty comes from recognizing that the problem requires multi-source BFS rather than running BFS from each water cell. Once that pattern is identified, the implementation is straightforward.
As Far from Land as Possible Python/Java solution
Most implementations follow the same multi-source BFS template. Initialize a queue with all land cells, perform BFS expansion in four directions, and track levels until no more water cells remain. The logic translates directly across Python, Java, C++, JavaScript, C#, and C with similar O(n^2) complexity.
How to solve As Far from Land as Possible in O(n^2)?
Push all land cells into a queue and run a multi-source BFS. Expand in four directions and mark visited water cells as you go. The BFS depth represents distance from land, so the final level reached before the queue empties is the maximum water distance. Since each cell is processed once, the algorithm runs in O(n^2).
What is the best approach for As Far from Land as Possible?
The best approach is multi-source Breadth-First Search (BFS). Start BFS simultaneously from every land cell and expand outward into water cells. Each BFS layer represents increasing Manhattan distance from land, and the last processed layer gives the maximum distance. This runs in O(n^2) time and O(n^2) space.
Is As Far from Land as Possible asked at Google/Amazon/Meta?
Grid BFS problems similar to this appear frequently in interviews at companies like Amazon, Google, and Meta. The key skill tested is recognizing multi-source BFS patterns in matrix problems. Variations also appear in shortest path and distance-to-nearest problems.
What data structure is used in As Far from Land as Possible?
The core data structure is a queue used for Breadth-First Search. The grid acts as both the input and a visited structure by marking processed water cells. The algorithm also relies on simple array traversal and directional offsets to explore neighbors in the matrix.
What is the time complexity of As Far from Land as Possible?
The optimal multi-source BFS solution runs in O(n^2) time because each grid cell is visited at most once. Space complexity is also O(n^2) due to the queue and visited tracking. A naive brute-force method that checks every water cell against every land cell can take up to O(n^4) time.