0314HardArrayBinary SearchDepth-First SearchBreadth-First SearchUnion-FindMinimaxHeap (Priority Queue)MatrixDijkstra's Algorithm

Cutter Power Setting

Tracked in this browser only

Write code

Trains the technique from

LeetCode 778Swim in Rising Water

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def min_power(hardness: list[list[int]]) -> int:

Java

public int minPower(int[][] hardness)

The intended approach

Time O(n^2 log n)Space O(n^2)

For any route, the setting it demands is the hardest cell on it, so the goal is the route whose hardest cell is as soft as possible. Expand cells in increasing order of that quantity with a min-heap: reaching a neighbour costs the larger of the current route's worst cell and the neighbour's own hardness. The first time the finish cell comes off the heap, its stored value is the smallest workable setting.

Pythonentry point: min_power

import heapq


def min_power(hardness):
    # Best-first search over cells, ordered by the hardest cell needed to reach them.
    # O(n^2 log n) time, O(n^2) space for the cost grid and the heap.
    n = len(hardness)
    need = [[-1] * n for _ in range(n)]
    need[0][0] = hardness[0][0]
    heap = [(hardness[0][0], 0, 0)]
    while heap:
        power, r, c = heapq.heappop(heap)
        if r == n - 1 and c == n - 1:
            return power
        if power > need[r][c]:
            continue
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr = r + dr
            nc = c + dc
            if 0 <= nr < n and 0 <= nc < n:
                cand = power if power > hardness[nr][nc] else hardness[nr][nc]
                if need[nr][nc] == -1 or cand < need[nr][nc]:
                    need[nr][nc] = cand
                    heapq.heappush(heap, (cand, nr, nc))
    return -1

The obvious version

Try every setting in increasing order, and for each one flood the slab from the start cell through the cells it opens, stopping at the first setting that reaches the finish.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_min_power(hardness):
    n = len(hardness)
    floor = hardness[0][0]
    if hardness[n - 1][n - 1] > floor:
        floor = hardness[n - 1][n - 1]
    for power in range(floor, n * n):
        seen = [[False] * n for _ in range(n)]
        seen[0][0] = True
        stack = [(0, 0)]
        while stack:
            r, c = stack.pop()
            if r == n - 1 and c == n - 1:
                return power
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr = r + dr
                nc = c + dc
                if 0 <= nr < n and 0 <= nc < n:
                    if not seen[nr][nc] and hardness[nr][nc] <= power:
                        seen[nr][nc] = True
                        stack.append((nr, nc))
    return -1

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
4 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in