As Far from Land as Possible
Medium · Graphs · Array · Dynamic Programming · Breadth-First Search · Matrix
Problem
You are given an n x n grid where 0 is water and 1 is land. Find the water cell whose distance to the nearest land cell is as large as possible, and return that distance.
Distance is Manhattan distance: |r0 - r1| + |c0 - c1|. If the grid has no land or no water at all, return -1.
Examples
Input: grid = [[1,0,0],[0,0,0],[0,0,0]] Output: 4
The bottom-right corner is 2 + 2 = 4 steps from the only land cell.
Input: grid = [[1,0,1],[0,0,0],[1,0,1]] Output: 2
The center cell is 2 away from every corner, and no water cell is farther.
Input: grid = [[1,1],[1,1]] Output: -1
There is no water cell, so the answer is -1.
Constraints
- n == len(grid) == len(grid[i])
- 1 <= n <= 100
- grid[i][j] is 0 or 1
Approaches
- Baseline: compare every water cell with every land cell — time O(n⁴), space O(n²) for the list of land cells
Follow-up
There is also a two-pass dynamic program: sweep top-left to bottom-right taking the distance from the up and left neighbors, then bottom-right to top-left with the down and right neighbors. It needs no queue. See the use cases for diagonal steps and for returning the whole distance map.
Related problems
Start free on Cariara · Coding problems · System design studio
