0604MediumArrayBinary SearchBreadth-First SearchUnion-FindHeap (Priority Queue)Matrix

Widest Margin Across the Block

Tracked in this browser only

Trains the technique from

LeetCode 2812Find the Safest Path in a Grid

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 city block is mapped as an n x n array of cells called grid. A cell holding 1 has a hazard standing in it and a cell holding 0 is empty. At least one cell holds a hazard.

A courier begins in the cell at row 0, column 0 and has to finish in the cell at row n - 1, column n - 1. One move takes the courier to a cell that shares an edge with the current cell and lies inside the block. Cells may be entered more than once, and a cell holding a hazard may be entered like any other.

The clearance of a cell is the smallest value of |r - hr| + |c - hc| over every hazard cell (hr, hc), where (r, c) is the cell itself. The margin of a walk is the smallest clearance found among the cells it enters, counting the first cell and the last cell.

Return the largest margin achievable by a walk from row 0, column 0 to row n - 1, column n - 1.

Examples

Example 1

Input: grid = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
Output: 1

The only hazard sits in the middle cell, whose clearance is 0. Both corners have clearance 2, and the walk down the left column then along the bottom row enters only cells of clearance 1 or more, so its margin is 1.

Example 2

Input: grid = [[1, 0], [0, 0]]
Output: 0

The starting cell itself holds the hazard, so its clearance is 0. Every walk begins there, which caps the margin at 0.

Example 3

Input: grid = [[0, 1, 0], [0, 0, 0], [0, 1, 0]]
Output: 1

Both corners of interest have clearance 1, and the middle cell of the grid also has clearance 1, so the walk through the middle row keeps a margin of 1.

Constraints

1 <= grid.length == n <= 400
grid[i].length == n
grid[i][j] is either 0 or 1.
At least one cell of the block holds a hazard.

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 maximum_safeness_factor(grid: list[list[int]]) -> int:

Java

public int maximumSafenessFactor(List<List<Integer>> grid)

The intended approach

Time O(n^2 log n): the expansion is O(n^2) and each of the O(log n) bisection steps runs an O(n^2) connectivity check.Space O(n^2) for the clearance labels and the visited marks.

Every cell is walkable, so the fewest sideways moves from a cell to a hazard equals the row gap plus the column gap to that hazard; a single layer-by-layer expansion started from all hazard cells at once therefore labels every cell with its clearance. With those labels in hand, ask a yes-or-no question instead: is there a walk that never enters a cell of clearance below `limit`? That is a plain connectivity check on the cells whose label is at least `limit`, run from an explicit stack. The answer to that question can only go from yes to no as `limit` grows, so bisect `limit` between `0` and `2 * (n - 1)` and keep the largest `limit` that still connects the two corners.

Pythonentry point: maximum_safeness_factor

def maximum_safeness_factor(grid):
    # O(n^2 log n) time: one multi-source sweep, then a reachability sweep per
    # bisection step. O(n^2) space. Nothing recurses, so a 400 x 400 block is fine.
    n = len(grid)
    steps = ((1, 0), (-1, 0), (0, 1), (0, -1))
    clearance = [[-1] * n for _ in range(n)]
    layer = []
    for r in range(n):
        for c in range(n):
            if grid[r][c] == 1:
                clearance[r][c] = 0
                layer.append((r, c))
    # Growing outward from every hazard at once labels each cell with the number
    # of sideways moves to the nearest hazard, which on an open grid is exactly
    # the row gap plus the column gap to that hazard.
    while layer:
        nxt = []
        for r, c in layer:
            here = clearance[r][c]
            for dr, dc in steps:
                nr = r + dr
                nc = c + dc
                if 0 <= nr < n and 0 <= nc < n and clearance[nr][nc] == -1:
                    clearance[nr][nc] = here + 1
                    nxt.append((nr, nc))
        layer = nxt

    def crossable(limit):
        if clearance[0][0] < limit or clearance[n - 1][n - 1] < limit:
            return False
        seen = [[False] * n for _ in range(n)]
        seen[0][0] = True
        stack = [(0, 0)]
        while stack:
            r, c = stack.pop()
            if r == n - 1 and c == n - 1:
                return True
            for dr, dc in steps:
                nr = r + dr
                nc = c + dc
                if (0 <= nr < n and 0 <= nc < n and not seen[nr][nc]
                        and clearance[nr][nc] >= limit):
                    seen[nr][nc] = True
                    stack.append((nr, nc))
        return False

    low = 0
    high = 2 * (n - 1)
    best = 0
    while low <= high:
        mid = (low + high) // 2
        if crossable(mid):
            best = mid
            low = mid + 1
        else:
            high = mid - 1
    return best

The obvious version

Fill the clearance of each cell by measuring it against every hazard cell in turn. Then relax a table of best-achievable margins: repeatedly push each cell's value into its four neighbours, capped by the neighbour's clearance, until a full sweep changes nothing. Because relaxation runs in every direction, walks that turn back on themselves are covered.

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_maximum_safeness_factor(grid):
    n = len(grid)
    hazards = []
    for r in range(n):
        for c in range(n):
            if grid[r][c] == 1:
                hazards.append((r, c))
    clearance = [[0] * n for _ in range(n)]
    for r in range(n):
        for c in range(n):
            closest = None
            for hr, hc in hazards:
                gap = abs(r - hr) + abs(c - hc)
                if closest is None or gap < closest:
                    closest = gap
            clearance[r][c] = closest
    reach = [[-1] * n for _ in range(n)]
    reach[0][0] = clearance[0][0]
    moving = True
    while moving:
        moving = False
        for r in range(n):
            for c in range(n):
                if reach[r][c] < 0:
                    continue
                for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    nr = r + dr
                    nc = c + dc
                    if 0 <= nr < n and 0 <= nc < n:
                        cand = reach[r][c]
                        if clearance[nr][nc] < cand:
                            cand = clearance[nr][nc]
                        if cand > reach[nr][nc]:
                            reach[nr][nc] = cand
                            moving = True
    return reach[n - 1][n - 1]

How this problem was checked

Reference solution executed against 11 test cases — 11 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