Maximum Safeness of a Grid Path
Updated
Problem statement
In an n by n binary grid, a 1 marks a thief and a 0 marks an empty cell. Travel from the top-left cell (0,0) to the bottom-right cell (n-1,n-1) by moving one cell up, down, left, or right. You may enter a cell containing a thief.
A cell's safety is its minimum Manhattan distance to any thief. The Manhattan distance from (r,c) to (x,y) is |r-x| + |c-y|. A path's safeness is the smallest cell safety anywhere on that path, including both endpoints.
Return the largest safeness achievable by any valid start-to-finish path. At least one thief exists, so every cell has a finite safety.
Function
maximumSafenessFactor(grid: List<List<Integer>>) → intExamples
Example 1
grid = [[0,0,1],[0,0,0],[0,0,0]]return = 2Take the left column and then the bottom row. Distances to the thief at (0,2) along this path are 2, 3, 4, 3, and 2. Its minimum is 2. Since the start has safety 2, no path can achieve more.
Example 2
grid = [[0,0],[0,1]]return = 0The finish contains a thief, so every path includes a cell of safety 0. Reaching the finish is allowed, and the best safeness is 0.
Constraints
1 <= grid.length <= 400.- Every row has exactly
grid.lengthcells. - Every cell is 0 or 1, and at least one cell is 1.
More Intuit Online Assessment questions
- Employee Promotion OpportunitiesOA · Seen Oct 2026
- Next Pascal Row CoefficientOA · Seen Oct 2026
- Parse Router LogsOA · Seen Oct 2026
- Longest Repeated Letter Block with Adjacent SwapsOA · Seen Oct 2026
- Maximum Square-Free DivisorOA · Seen Oct 2026
- Two Tribes from Taller-Person CountsOA · Seen Oct 2026
- Shortest Path from an Encoded GraphOA · Seen Sep 2026
- Oldest and Youngest EmployeesOA · Seen Sep 2026
- Pressure-Isolation Shutdown OrderOA · Seen Sep 2026
- Submask Sum QueriesOA · Seen Sep 2026
Similar questions at other companies
- Course Schedule IIChainalysis · OAChainalysis interview questions
- Satellite Network Message PropagationOptiver · OAOptiver interview questions
- Avoiding the Obstacles (IMC Sydney 🦪)IMC Trading · OAIMC Trading interview questions
- Course Schedule IIAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Shortest Travel Time in a Grid with Traffic LightsWaymo · PHONE SCREENWaymo interview questions
- Find a Valid Course Completion OrderGoogle · ONSITE INTERVIEWGoogle interview questions
- Course Schedule IIWalmart · ONSITE INTERVIEWWalmart interview questions
- Minimum Flood Level to Disconnect a GridMeta · ONSITE INTERVIEWMeta interview questions
- Task Order With PrerequisitesDoorDash · PHONE SCREEN · ONSITE INTERVIEWDoorDash interview questions
- Course Schedule IIBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions