Route With the Highest Bottleneck

Medium

You are given a rectangular grid of integers heights. You need to travel from the top-left corner (0, 0) to the bottom-right corner, each time moving to an adjacent cell up, down, left or right. The *bottleneck* of a route is the smallest number among all its cells, including the first and the last. For example, the route 8 → 4 → 5 → 9 has a bottleneck of 4. Return the largest bottleneck achievable by any route.

Example 1

heights=[[6, 2, 7], [5, 8, 3], [1, 4, 9]] → 4

The route 6 → 5 → 8 → 4 → 9 has a minimum of 4. Any other route touches 1, 2 or 3, so 4 is the best possible.

Example 2

heights=[[3, 9, 9], [9, 9, 2]] → 2

Both corner cells lie on every route, and the smaller of them is 2, so the answer is 2.

Example 3

heights=[[1, 7], [7, 7]] → 1

Constraints

1 ≤ number of rows, number of columns ≤ 100
The grid has at least two cells
0 ≤ heights[i][j] ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Breadth-First Search Union Find Array Binary Search Matrix Heap (Priority Queue)

Similar problems

The Gentlest Climb Medium Crossing at High Tide Hard Steer Clear of the Sentries Medium Last Dry Crossing Day Hard Drain the Landlocked Ponds Medium

Input

heights=[[6, 2, 7], [5, 8, 3], [1, 4, 9]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 75 tests on the server, hidden ones included.