1031MediumArrayDynamic ProgrammingBreadth-First SearchMatrix

The Most Sheltered Berth

Tracked in this browser only

Trains the technique from

LeetCode 1162As Far from Land as Possible

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A square chart chart marks each cell 1 for land or 0 for water. A step goes between cells sharing an edge, over land or water alike, and the distance between two cells is the fewest steps between them.

Return the largest distance any water cell sits from its nearest land cell. When the chart is all land or all water, return -1.

Examples

Example 1

Input: chart = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
Output: 2

The single land cell sits in the middle. Each corner is two steps from it, one across and one down, and nothing on the chart is farther.

Example 2

Input: chart = [[1, 1, 1], [1, 1, 1], [1, 1, 1]]
Output: -1

There is no water anywhere, so there is no berth to measure.

Example 3

Input: chart = [[0, 0, 0, 1], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
Output: 6

The only land sits in the top-right corner, so the bottom-left corner is the farthest berth, three steps down and three across.

Constraints

1 <= chart.length <= 100
Every row of chart is as long as the chart is tall.
0 <= chart[i][j] <= 1

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def max_distance(chart: list[list[int]]) -> int:

Java

public int maxDistance(int[][] chart)

The intended approach

Time O(n^2) over the chart's cells.Space O(n^2) for the queue and the marks.

Measuring each water cell against the land separately would cost the chart's size once per cell. Instead flood outward from every land cell at the same time. Put all the land cells into a queue at a distance of nothing and mark them seen. Then take cells off the front and step to their unseen neighbours, handing each a distance one greater and marking it. Because all the land started together, the distance a water cell receives is its distance to the nearest land, not merely to whichever land the wave happened to leave from. The largest distance handed out is the answer. A queue that starts empty means no land, and one that starts holding every cell means no water; both answer `-1`. Each cell joins the queue once, so this is a single pass over the chart.

Pythonentry point: max_distance

def max_distance(chart):
    from collections import deque
    n = len(chart)
    cols = len(chart[0])
    seen = [[False] * cols for _ in range(n)]
    queue = deque()
    for r in range(n):
        for c in range(cols):
            if chart[r][c] == 1:
                seen[r][c] = True
                queue.append((r, c, 0))
    if not queue or len(queue) == n * cols:
        return -1
    best = 0
    while queue:
        r, c, far = queue.popleft()
        if far > best:
            best = far
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr = r + dr
            nc = c + dc
            if nr < 0 or nr >= n or nc < 0 or nc >= cols:
                continue
            if seen[nr][nc]:
                continue
            seen[nr][nc] = True
            queue.append((nr, nc, far + 1))
    return best

The obvious version

Since every cell can be stepped over, the distance between two cells is simply their rows apart plus their columns apart. So gather the land cells and the water cells, and for each water cell measure it against every land cell, keeping the nearest, then take the largest of those. Costs the water cells times the land cells rather than one flood.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_max_distance(chart):
    n = len(chart)
    cols = len(chart[0])
    land = []
    water = []
    for r in range(n):
        for c in range(cols):
            if chart[r][c] == 1:
                land.append((r, c))
            else:
                water.append((r, c))
    if not land or not water:
        return -1
    best = 0
    for wr, wc in water:
        near = None
        for lr, lc in land:
            gap = abs(wr - lr) + abs(wc - lc)
            if near is None or gap < near:
                near = gap
        if near > best:
            best = near
    return best

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in