Katkat
Back

Maximize the minimum value along a grid path

CrowdstrikeSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to combine binary search on the answer with graph traversal techniques (BFS/DFS/Union-Find) to solve optimization problems on a 2D grid.

Problem: Maximize the Minimum Path Value

You are given an n x m grid of integers, where grid[i][j] represents the safety score of the cell at row i and column j. You start at the top-left corner (0, 0) and want to reach the bottom-right corner (n-1, m-1).

A path consists of moving to adjacent cells (up, down, left, right). The score of a path is defined as the minimum integer value encountered among all cells visited in that path. Your goal is to find a path from the start to the end such that the path score is maximized.

Implement the function: def max_min_path(grid: List[List[int]]) -> int:

Constraints

  • n, m are between 1 and 500.
  • grid[i][j] is between 0 and 1,000,000.

Examples

Example 1:

Input: grid = [[5, 1], [4, 5]]
Output: 4
Explanation: The path [(0,0), (1,0), (1,1)] has values [5, 4, 5]. The minimum is 4. Any other path includes the 1, resulting in a lower score.

Example 2:

Input: grid = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Output: 3
Explanation: The path using cells [1, 2, 3, 6, 9] yields a minimum of 1, but we can traverse through higher numbers such as [1, 4, 7, 8, 9] or [1, 2, 5, 8, 9]. However, the 'bottleneck' cell limits the score.

Edge Cases

  • A 1x1 grid.
  • Grids where all values are the same.
  • Paths that must pass through very low-value cells.

Hints

Hint 1

Consider that if you can reach the destination with a path score of at least 'X', you can also reach it with any score less than 'X'.

Hint 2

This monotonicity allows you to binary search on the possible answer values ranging from the minimum to the maximum value in the grid.

Hint 3

For a fixed value 'K' in your binary search, use BFS or DFS to check if a path exists from start to end using only cells with values >= K.

Follow-up questions

  • How would you solve this if you were allowed to move diagonally as well?
  • Could you solve this using a modified version of Dijkstra’s algorithm or Prim’s algorithm?
  • What is the time complexity of your solution, and how does it change if we use the Union-Find data structure instead of BFS/DFS?