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

1. Problem Statement

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.

1. The Priority Queue: Use a Min-Heap storing {row, col, max_elevation_so_far}. The heap sorts by max_elevation_so_far.
2. 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

1. 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.
2. 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.
3. 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."