PPractick

The problem

A flooded square plaza is an n × n grid of distinct elevations. Rain raises the water level: at time t, water stands at height t everywhere, and a swimmer can move 4-directionally between cells whose elevations are at most t (swimming takes no time). Starting at the top-left cell, what's the earliest time to reach the bottom-right cell? A path is usable at time t exactly when its highest cell is at most t, so the answer is the minimum over paths of the path's maximum elevation. That's Dijkstra with max instead of sum.

Example: [[0,2], [1,3]] → 3.

Function signature

int swimInWater(const vector<vector<int>>& grid);  // n x n, distinct values 0..n²-1

Test cases

Input	Output	Explanation
[[0,2],[1,3]]	3	The goal itself is at 3
[[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]	16	The best path's peak is 16
[[3,2],[0,1]]	3	The start itself is at 3
[[0,1],[2,3]]	3
[[0]]	0

(Confirm: moves are 4-directional; you can wait anywhere; both the start and goal cells count toward the maximum.)

How interviewers phrase it

• "At time t, you can swim between adjacent squares if both elevations are at most t. Return the least time until you can reach the bottom-right square from the top-left" (LeetCode 778).

Clarifying questions to ask

1. Does the start cell's elevation count? (Yes: you can't be in the water there until t reaches it.)
2. 4-directional? (Yes.)
3. How large? (n ≤ 50, and values are a permutation of 0..n² − 1.)

Follow-ups to expect

1. "Why is this a minimax path problem?"
2. "Why does Dijkstra work with max?"
3. "Binary search alternative?"
4. "Union-find alternative?"
5. "Complexity?"

Related questions

• Path with minimum effort Hard
• Search in a 2D matrix Medium
• Search in 2D matrix - II Medium
• Find Peak Element - II Medium
• Matrix Median Medium
• Rotten Oranges Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in