Rising Tide Crossing
Problem
A flooded field is a grid of ground heights, and the water level rises steadily from 0. A rescue boat can float over any cell whose ground height is at most the current water level, and it moves up, down, left or right between floatable cells. Return the lowest water level at which the boat can travel from the top-left cell to the bottom-right cell. The grid has at least one cell, and heights are whole numbers from 0 upward.
Examples
Input: heights = [[1, 5, 2],
[2, 9, 1],
[3, 4, 1]]
Output: 4
Why: down the left edge and along the bottom, the highest ground is 4Input: heights = [[0, 2],
[1, 3]]
Output: 3
Why: the destination itself sits at height 3Input: heights = [[7]]
Output: 7
Why: edge case, start and finish are the same cellHints
0 / 3
The cost of a route is not a sum. It is the highest cell along it, and you want the route whose highest cell is as low as possible.
Instead of searching for a route, flood the field yourself: open the cells from lowest to highest and watch when the two corners first become connected.
Sort the cells by height and open them one at a time, joining each new cell with any open neighbour in a union-find structure. The height of the cell that first puts both corners in the same set is the answer, the same way Kruskal adds the cheapest edges until the tree connects.
Solution
A route is usable at level t exactly when every cell on it is at most t, so the answer is the smallest possible maximum height along any route. Opening cells in increasing height, as Kruskal adds edges in increasing weight, and joining each one with its already-open neighbours keeps track of which open cells are connected. The moment the two corners share a set, the cell just opened is the highest one any route needs. Time is O(rc log rc) for sorting r times c cells, and space is O(rc).
def lowest_crossing_level(heights):
rows, cols = len(heights), len(heights[0])
parent = list(range(rows * cols))
def find(x): # union-find root with path halving
while parent[x] != x:
parent[x] = parent[parent[x]]; x = parent[x]
return x
opened = set()
for h, r, c in sorted((heights[r][c], r, c) for r in range(rows) for c in range(cols)):
opened.add((r, c)) # the tide reaches h and this cell floats
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if (nr, nc) in opened:
parent[find(nr * cols + nc)] = find(r * cols + c)
if find(0) == find(rows * cols - 1): # the corners just joined up
return h
print(lowest_crossing_level([[1, 5, 2], [2, 9, 1], [3, 4, 1]])) # -> 4
print(lowest_crossing_level([[0, 2], [1, 3]])) # -> 3
print(lowest_crossing_level([[7]])) # -> 7Stuck on the idea rather than the code? Kruskal's Spanning Tree covers it.