As Far from Land as Possible - Solution & Explanation
Problem Statement
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.
The function uses a queue to implement BFS starting from all land cells. The queue holds the coordinates of the cells to be processed next. It explores all grid cells using BFS and calculates the maximum distance from the nearest land cell to a water cell.
Complexity
The time complexity is O(n2), where n is the dimension of the grid, as each cell is visited once. The space complexity is also O(n2) due to the queue that can store all cells in the grid.
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.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) Approach | The time complexity is O(n2), where n is the dimension of the grid, as each cell is visited once. The space complexity is also O(n2) due to the queue that can store all cells in the grid. |
| BFS | — |
Detailed 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 |
Video Solution
As Far from Land as Possible - Leetcode 1162 - Python • NeetCodeIO • 13,277 views views
Watch 9 more video solutions →Frequently Asked Questions
Is As Far from Land as Possible easy or hard?
As Far from Land as Possible Python/Java solution
How to solve As Far from Land as Possible in O(n^2)?
What is the best approach for As Far from Land as Possible?
Is As Far from Land as Possible asked at Google/Amazon/Meta?
What data structure is used in As Far from Land as Possible?
What is the time complexity of As Far from Land as Possible?
Ready to solve this problem?
Practice As Far from Land as Possible with our built-in code editor and test cases.
Practice on FleetCode