Grid Path With the Most Clearance
Updated
Problem statement
You are given a grid grid with m rows and n columns. A cell with 0 is open and a cell with 1 is blocked.
You walk from the top-left cell (0, 0) to the bottom-right cell (m - 1, n - 1). Each move goes one cell up, down, left or right. You may only stand on open cells, and both the start and the end must be open.
The clearance of a cell (r, c) is its distance to the nearest blocked cell, measured as |r - x| + |c - y| for a blocked cell (x, y). The distance is measured straight across the grid, not along a walking route. The clearance of a path is the smallest clearance among all cells on it, including the start and the end.
Return the largest clearance any path can have. If there is no path from the start to the end, return -1.
Function
maxPathClearance(grid: int[][]) → intExamples
Example 1
grid = [[0,0,0,0,0,0],[0,0,0,0,1,0],[0,0,0,0,0,0],[0,1,0,0,0,0],[0,0,0,0,0,0]]return = 2The blocked cells are (1, 4) and (3, 1).
- Walking along the top row and down the right column passes
(0, 4), which is next to(1, 4), so that path scores only1. Walking down the left column and along the bottom row passes(3, 0), next to(3, 1), so it also scores1. - The path
(0, 0),(0, 1),(0, 2),(1, 2),(2, 2),(2, 3),(3, 3),(4, 3),(4, 4),(4, 5)goes between the two blocked cells. Its closest cells, such as(1, 2)and(2, 2), are2away, so it scores2. - The cells
3or more away form two groups, one around the start and one around the end. They do not touch, so no path scores3.
The answer is 2.
Example 2
grid = [[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[1,0,0,0,0,0]]return = 3The only blocked cell is (3, 0). The start (0, 0) is 3 away from it, so no path can score more than 3.
Walk right along the top row, then down the last column. The top row cells are 3 to 8 away, and the last column cells are 5 to 8 away. The lowest value on this path is 3, at the start, so the answer is 3.
Example 3
grid = [[0,0,1],[0,1,0],[1,0,0]]return = -1The blocked cells (0, 2), (1, 1) and (2, 0) form a diagonal line. From the start you can reach only (0, 1) and (1, 0), and every other neighbor of those cells is blocked. You cannot move diagonally, so the end (2, 2) cannot be reached and the answer is -1.
Constraints
1 <= grid.length <= 1001 <= grid[i].length <= 100- Every row has the same length.
- Each
grid[i][j]is0or1. - At least one cell is
1.
More DocuSign Online Assessment questions
- Max Sum With No Two Adjacent PicksOA · Seen Apr 2026
- Max Sum With No Two Adjacent Picks on a CircleOA · Seen Apr 2026
- Beautiful Number OrderingsOA · Seen Feb 2026
- Vehicle Mixes for a Wheel TotalOA · Seen May 2025
- Count Sales Rung Up at the Wrong PriceOA · Seen Feb 2021
- Most Disjoint Intervals From Starts and DurationsOA · Seen Feb 2021
- Fewest Fountains to Water the GardenOA · Seen Feb 2021
- Lowest Start That Keeps Running Totals PositiveOA · Seen Feb 2021
- Fewest Student Groups Within a Level GapOA · Seen Nov 2020
- Alphabetize a Word ListOA · Seen May 2020
Similar questions at other companies
- Find the Safest Path in a GridAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Shortest Path Around Rectangular ObstaclesDRW · OADRW interview questions
- House Bounds in a Ragged GridRippling · OA · PHONE SCREENRippling interview questions
- Maximum Damage PatchGecko Robotics · OA · PHONE SCREEN
- Largest Square Sub-Grid Within a Sum LimitC3.ai · OAC3.ai interview questions
- Avoiding the Obstacles (IMC Sydney 🦪)IMC Trading · OAIMC Trading interview questions
- Find Maximum DistanceWells Fargo · OAWells Fargo interview questions
- Rotting OrangesSalesforce · ONSITE INTERVIEWSalesforce interview questions
- Search a Row- and Column-Sorted MatrixByteDance · ONSITE INTERVIEWByteDance interview questions
- Max Area of Island Without Changing the GridFlexport · PHONE SCREENFlexport interview questions