Path With Maximum Minimum Value

MediumGraphsdijkstra

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given an m x n integer grid. A path starts at the top-left cell (0, 0), ends at the bottom-right cell (m - 1, n - 1), and moves one step at a time up, down, left or right. The score of a path is the smallest value among all cells it visits, including both endpoints. Return the highest score achievable by any path.

Examples

Input: grid = [[5,4,5],[1,2,6],[7,4,6]]
Output: 4
The path 5 -> 4 -> 5 -> 6 -> 6 never drops below 4, and every path must pass through a cell of value at most 4.
Input: grid = [[2,2,1,2,2,2],[1,2,2,2,1,2]]
Output: 2
Walk along the 2s, zig-zagging between the rows to avoid the 1s.

Constraints

  • 1 <= m, n <= 100
  • 0 <= grid[i][j] <= 10^9

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More dijkstra problems