Core Insight Improve a node’s known cost only when a newly discovered path is genuinely better.
Common Pitfall Discard stale priority-queue entries instead of expanding them a second time.
Description
Minimize the time to swim from top-left to bottom-right.
Constraints
- Time Complexity:
O(n² log n) - Space Complexity:
O(n²)
Tags
arraybinary-searchdfsbfsunion-findgraphheapmatrix
Implementation Plan Translate the invariant into these small, testable moves.
- Initialize distances and a frontier.
- Take the cheapest candidate.
- Relax each outgoing edge.
- Repeat until the target or all reachable nodes are settled.
def swimInWater(grid):
N = len(grid)
visit = set()
minH = [[grid[0][0], 0, 0]]
directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
visit.add((0, 0))
while minH:
t, r, c = heapq.heappop(minH)
if r == N - 1 and c == N - 1:
return t
for dr, dc in directions:
neiR, neiC = r + dr, c + dc
if (neiR < 0 or neiR == N or
neiC < 0 or neiC == N or
(neiR, neiC) in visit):
continue
visit.add((neiR, neiC))
heapq.heappush(minH, [max(t, grid[neiR][neiC]), neiR, neiC])