Minimize Max Risk Path
As a senior engineer at Uber, you're tasked with optimizing driver safety for Uber Eats deliveries. Drivers navigate through a city represented as a grid, where each cell has an associated 'risk level' (e.g., due to traffic, construction, or other hazards). The goal is to find a delivery route from a starting depot to a customer's location such that the maximum risk encountered on any segment of the path is minimized. This ensures drivers can choose the safest possible route, even if it means a slightly longer journey, improving overall driver experience and operational reliability.
Implement a function minMaxRiskPath that calculates the minimum possible value for the highest risk encountered on any valid path from a specified start point to a target destination within a given city grid.
Input:
grid: A number[][] representing the city map. grid[r][c] denotes the risk level associated with the cell at row r and column c.start: A [number, number] tuple [startRow, startCol] indicating the starting coordinates of the driver.target: A [number, number] tuple [targetRow, targetCol] indicating the destination coordinates.Output:
number representing the minimum possible value for the maximum risk encountered on any path from start to target.start and target coordinates are guaranteed to be within the bounds of the grid.start to target always exists.Examples
Example 1
Input:
grid = [[0, 1, 2], [5, 4, 3], [6, 7, 8]], start = [0, 0], target = [1, 1]
Output:
4
Note:
Path (0,0) -> (0,1) -> (1,1) has risks [0, 1, 4]. Max risk is 4. Path (0,0) -> (1,0) -> (1,1) has risks [0, 5, 4]. Max risk is 5. The minimum of these maximums is 4.
Example 2
Input:
grid = [[10, 2, 3], [4, 5, 6], [7, 8, 9]], start = [0, 0], target = [2, 2]
Output:
10
Note:
Any path from [0,0] must start at grid[0][0] which has a risk of 10. Thus, the minimum possible maximum risk on any path will be at least 10.
Example 3
Input:
grid = [[1, 100, 1], [1, 100, 1], [1, 1, 1]], start = [0, 0], target = [2, 2]
Output:
1
Note:
A path like (0,0) -> (1,0) -> (2,0) -> (2,1) -> (2,2) has risks [1, 1, 1, 1, 1]. The maximum risk on this path is 1. This path successfully navigates around the high-risk cells (100) in the middle column.
Constraints
1 <= grid.length, grid[0].length <= 200 (i.e., M, N dimensions of the grid)0 <= grid[r][c] <= 1000 for all cells (r, c)start and target are valid coordinates within the grid boundaries.start/target coordinates.Loading editor...