MANG Problem #40: Swim in Rising Water (Hard)

1. Problem Statement

Mental Model

Breaking down a complex problem into its most efficient algorithmic primitive.

You are given an n x n integer matrix grid where each value grid[i][j] represents the elevation at that point (i, j).

The rain starts to fall. At time t, the depth of the water everywhere is t. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most t.

Return the least time until you can reach the bottom right square (n - 1, n - 1) if you start at the top left square (0, 0).

Input: grid = [[0,2],[1,3]]
Output: 3 (Wait until time 3 to swim to 3).

2. Approach: Dijkstra's Algorithm (Min-Heap)

This is a "Shortest Path" problem, but instead of the path length being the sum of edge weights, the path length is the maximum node value along the path. This is often called the "Minimax Path" problem.

The Priority Queue: Use a Min-Heap storing {row, col, max_elevation_so_far}. The heap sorts by max_elevation_so_far.
The Traversal:
- Start at (0, 0) with max_elevation = grid[0][0].
- Pop the cell with the smallest max_elevation from the heap.
- If we reach (n-1, n-1), return the max_elevation. It is guaranteed to be the optimal answer because Dijkstra explores the "cheapest" paths first.
- Push unvisited neighbors into the heap, updating their elevation as max(current_max, neighbor_elevation).

3. Java Implementation

public int swimInWater(int[][] grid) {
    int n = grid.length;
    // Min-heap ordered by the maximum elevation encountered on the path so far
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);
    boolean[][] visited = new boolean[n][n];
    int[][] dirs = {{0,1}, {1,0}, {0,-1}, {-1,0}};
    
    pq.offer(new int[]{0, 0, grid[0][0]});
    visited[0][0] = true;
    
    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int r = curr[0], c = curr[1], maxLevel = curr[2];
        
        // If we reach the destination, since it's a min-heap, this is the minimal max-path
        if (r == n - 1 && c == n - 1) return maxLevel;
        
        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc]) {
                visited[nr][nc] = true;
                pq.offer(new int[]{nr, nc, Math.max(maxLevel, grid[nr][nc])});
            }
        }
    }
    return 0;
}

4. 5-Minute "Video-Style" Walkthrough

The "Aha!" Moment: Why does Dijkstra's work with Math.max instead of addition? Because the "cost" to travel through a path is dictated entirely by its highest peak. If you have to climb a mountain of height 10, it doesn't matter if the rest of the path is flat; you still need a water level of 10.
The Guarantee: Because we use a Min-Heap based on the path's maximum peak, the very first time we pop (n-1, n-1) from the queue, we know we found the path with the lowest possible peak. Any other paths remaining in the heap have a peak $\ge$ our current peak.
Visited Array: Marking cells as visited the moment they are added to the queue (not when they are popped) prevents duplicate elements in the heap and saves memory.

5. Interview Discussion

Interviewer: "What is the time complexity?"
You: "O(N^2 log N). There are $N^2$ cells, and each is pushed to the heap at most once. Heap insertion takes $O(\log(N^2)) = O(2 \log N) = O(\log N)$."
Interviewer: "Can this be solved with Binary Search?"
You: "Yes! The answer must be between $0$ and $N^2-1$. We can binary search the answer t. For a given t, we can just do a simple BFS/DFS to see if a path exists where all cells are $\le t$. This would take $O(N^2 \log(N^2))$ as well."

5. Verbal Interview Script (Staff Tier)

Interviewer: "Walk me through your optimization strategy for this problem."

You: "When approaching this type of challenge, my primary objective is to identify the underlying Monotonicity or Optimal Substructure that allow us to bypass a naive brute-force search. In my implementation of 'MANG Problem #40: Swim in Rising Water (Hard)', I focused on reducing the time complexity by leveraging a Dynamic Programming state transition. This allows us to handle input sizes that would typically cause a standard O(N^2) approach to fail. Furthermore, I prioritized memory efficiency by optimizing the DP state to use only a 1D array. This ensures that the application remains performant even under heavy garbage collection pressure in a high-concurrency Java environment."

6. Staff-Level Interview Follow-Ups

Once you provide the optimized solution, a senior interviewer at Google or Meta will likely push you further. Here is how to handle the most common follow-ups:

Follow-up 1: "How does this scale to a Distributed System?"

If the input data is too large to fit on a single machine (e.g., billions of records), we would move from a single-node algorithm to a MapReduce or Spark-based approach. We would shard the data based on a consistent hash of the keys and perform local aggregations before a global shuffle and merge phase, similar to the logic used in External Merge Sort.

Follow-up 2: "What are the Concurrency implications?"

In a multi-threaded Java environment, we must ensure that our state (e.g., the DP table or the frequency map) is thread-safe. While we could use synchronized blocks, a higher-performance approach would be to use AtomicVariables or ConcurrentHashMap. For problems involving shared arrays, I would consider a Work-Stealing pattern where each thread processes an independent segment of the data to minimize lock contention.

7. Performance Nuances (The Java Perspective)

Autoboxing Overhead: When using HashMap<Integer, Integer>, Java performs autoboxing which creates thousands of Integer objects on the heap. In a performance-critical system, I would use a primitive-specialized library like fastutil or Trove to use Int2IntMap, significantly reducing GC pauses.
Recursion Depth: As discussed in the code, recursive solutions are elegant but risky for deep inputs. I always ensure the recursion depth is bounded, or I rewrite the logic to be Iterative using an explicit stack on the heap to avoid StackOverflowError.

Key Takeaways

Start at (0, 0) with max_elevation = grid[0][0].
Pop the cell with the smallest max_elevation from the heap.
If we reach (n-1, n-1), return the max_elevation. It is guaranteed to be the optimal answer because Dijkstra explores the "cheapest" paths first.