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] is 0 or 1The key idea in #1162 As Far from Land as Possible is to find the ocean cell that has the maximum distance from any land cell in a grid. Instead of calculating the distance from each water cell separately, an efficient strategy is to reverse the thinking.
A common optimal method uses multi-source Breadth-First Search (BFS). First, push all land cells into a queue and expand outward layer by layer into water cells. Each BFS level represents increasing distance from land, so the last expanded water cell gives the farthest distance.
Another conceptual approach involves dynamic programming with two grid passes, where distances are updated based on neighboring cells in forward and backward sweeps. This propagates the shortest distance from land across the grid.
The BFS solution is typically preferred due to its clarity and natural fit for grid expansion problems. Both strategies process each cell a limited number of times, giving O(n²) time complexity for an n x n grid and similar space usage for tracking distances or queue states.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Multi-source BFS | O(n²) | O(n²) |
| Dynamic Programming (Two-Pass Grid) | O(n²) | O(n²) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Can you think of this problem in a backwards way ?
Imagine expanding outward from each land cell. What kind of search does that ?
Use BFS starting from all land cells in the same time.
When do you reach the furthest water cell?
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 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.
1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4#include <string.h>
5#define MAXN
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.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Multi-source BFS allows us to treat all land cells as starting points simultaneously. This ensures that each water cell gets the shortest possible distance from the nearest land without repeatedly recalculating distances.
Yes, grid-based BFS and distance propagation problems like this are common in technical interviews at companies such as Amazon, Google, and Meta. They test understanding of graph traversal, matrix processing, and algorithm optimization.
The optimal approach uses multi-source Breadth-First Search (BFS). All land cells are added to the queue initially, and BFS expands outward to water cells layer by layer. The last distance reached during this expansion represents the farthest ocean cell from land.
Yes, a dynamic programming approach can propagate minimum distances using two passes over the grid. Each cell updates its distance based on neighboring cells, first from top-left to bottom-right and then in reverse.