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.

Description Hints 4 Solution Video 12:16

1162. As Far from Land as Possible

Medium52.2% acceptance7 companies

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.length
n == grid[i].length
1 <= n <= 100
grid[i][j] is 0 or 1

Asked at 7 companies

UiPath Hive Wix Tiktok

Google Amazon Microsoft

Topics

Hints open one at a time

Hint 1

Can you think of this problem in a backwards way ?

Hint 2

Imagine expanding outward from each land cell. What kind of search does that ?

Hint 3

Use BFS starting from all land cells in the same time.

Hint 4

When do you reach the furthest water cell?

12:16

Still stuck?Read 2 approaches, or watch a walkthrough.

Open solution