Frontend School

Minimize Max Risk Path

DSA
medium

Minimize Max Risk Path

Medium
Matrix
Graph
Dijkstra
BFS
Binary Search

Overview

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.

What you need to do / Task

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 & output

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:

  • A number representing the minimum possible value for the maximum risk encountered on any path from start to target.

Clarifications

  • Drivers can move in four cardinal directions: up, down, left, and right.
  • The start and target coordinates are guaranteed to be within the bounds of the grid.
  • The risk value of a cell is considered part of the path's maximum risk if the path passes through that cell.
  • Assume that a path from start to target always exists.

Examples

1

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.

2

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.

3

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

Constraints & assumptions

  • 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.
  • A path must stay within the grid boundaries.

Out of scope

  • Optimizing for the shortest path length (only the maximum risk on the path matters).
  • Handling invalid input formats or out-of-bounds start/target coordinates.
  • Dynamic changes in risk levels or multiple concurrent deliveries.

What interviewers evaluate

  • Correctness and robustness of the algorithm to find the minimum maximum-risk path.
  • Efficiency of the solution in terms of time and space complexity.
  • Clarity and structure of the code, including appropriate data structures.
  • Ability to articulate the chosen approach and justify design decisions.

Loading editor...