Show problems as
Classic problem #778HardArrayBinary SearchDepth-First SearchBreadth-First SearchUnion-FindMinimaxHeap (Priority Queue)MatrixDijkstra's Algorithm

Swim in Rising Water

Real-world version: Cutter Power Setting
Tracked in this browser only
Read Swim in Rising Water on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A tunnelling machine has to cut a channel across a square slab. The slab is mapped as an n x n grid, and hardness[r][c] is the rock hardness of the cell in row r, column c. Every hardness value in the slab is different.

The machine's cutting head runs at a whole-number power setting. At setting p the head can occupy any cell whose hardness is at most p, and it can step from its current cell to a cell sharing an edge with it: up, down, left or right. Diagonal steps are not possible. The power setting is chosen once, before the run, and stays fixed for the whole crossing. Steps themselves take no time, so the only question is which cells are open.

The head starts on cell (0, 0) and must finish on cell (n - 1, n - 1), and both of those cells have to be open at the chosen setting.

Return the smallest power setting that lets the head get from the start cell to the finish cell.

Examples

Example 1

Input
hardness = [[0, 3], [2, 1]]
Output
2

At setting 2 the head runs (0, 0) -> (1, 0) -> (1, 1), and the hardest cell on that route is the 2 at (1, 0). At setting 1 the head cannot leave the start, because its two neighbours have hardness 3 and 2.

Example 2

Input
hardness = [[1, 0], [2, 3]]
Output
3

The finish cell has hardness 3, so the setting has to be at least 3, and at 3 the route (0, 0) -> (0, 1) -> (1, 1) is open.

Example 3

Input
hardness = [[0, 1, 2], [7, 8, 3], [6, 5, 4]]
Output
4

At setting 4 the head follows the hardnesses 0, 1, 2, 3, 4 across the top row and down the right column. The finish cell has hardness 4, so the setting cannot be lower.

Example 4

Input
hardness = [[0, 7, 8], [6, 5, 1], [2, 3, 4]]
Output
6

At setting 6 the head goes down the left column through hardnesses 0, 6, 2 and then right along the bottom row through 3 and 4. At setting 5 the start cell is sealed in, since its only neighbours have hardness 7 and 6.

Constraints

  • n == hardness.length
  • n == hardness[i].length
  • 1 <= n <= 50
  • 0 <= hardness[r][c] < n^2
  • Every value hardness[r][c] is unique.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def min_power(hardness: list[list[int]]) -> int:
Java
public int minPower(int[][] hardness)

More on the same topics