Wading Across a Flooding Field
Solve this ProblemA field is described by a grid of elevations. As time passes, every cell whose elevation is at most t floods, and you can walk between flooded cells that share a side. Find the earliest time at which you can walk from the top-left cell to the bottom-right cell.
The answer is the smallest possible height of the highest cell on a route. Flooding the cells from lowest to highest and merging neighbouring flooded cells with union-find finds the exact moment the two corners become connected.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ rows, cols ≤ 8; 0 ≤ elevation[r][c] ≤ 99 (values may repeat) - ◆
At time t every cell with elevation ≤ t is flooded to knee height; you may stand on and walk between flooded cells that share a side (up, down, left, right) - ◆
You start on the top-left cell and want to reach the bottom-right cell; both must also be flooded - ◆
Return the earliest time t at which such a walk exists (equivalently, the smallest possible value of the highest cell on any route)
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Try Every Water Level With a Flood Search
BruteTry the times t = 0, 1, 2, … in order. For each t, run a breadth-first search from the start that may only enter flooded cells (elevation ≤ t) and see whether it reaches the destination. The first t for which it does is the answer. At most H = 100 different values of t are tried, each search costs O(R·C).
O(H · R·C)O(R·C)1class Solution {
2 private boolean canCross(int[][] elevation, int level) {
3 int rows = elevation.length, cols = elevation[0].length;
4 if (elevation[0][0] > level) return false;
5 int[] dr = {1, -1, 0, 0};
6 int[] dc = {0, 0, 1, -1};
7 boolean[][] seen = new boolean[rows][cols];
8 Deque<int[]> queue = new ArrayDeque<>();
9 seen[0][0] = true;
10 queue.add(new int[]{0, 0});
11 while (!queue.isEmpty()) {
12 int[] cell = queue.poll();
13 for (int d = 0; d < 4; d++) {
14 int nr = cell[0] + dr[d], nc = cell[1] + dc[d];
15 if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && !seen[nr][nc] && elevation[nr][nc] <= level) {
16 seen[nr][nc] = true;
17 queue.add(new int[]{nr, nc});
18 }
19 }
20 }
21 return seen[rows - 1][cols - 1];
22 }
23
24 public int floodLevel(int[][] elevation) {
25 for (int level = 0; level <= 99; level++) {
26 if (canCross(elevation, level)) return level;
27 }
28 return 99;
29 }
30}Optimal — Flood Cells in Order of Height With Union-Find
OptimalSort the cells by elevation and "flood" them one at a time, lowest first. Each time a cell is flooded, merge it (union-find) with every already flooded neighbour, so a group always means "cells connected by flooded cells". After each flooding, check whether the start and the destination are in the same group; the elevation of the cell just flooded is then the answer, because no route can avoid a cell of that height. Sorting dominates the time.
O(R·C · log(R·C))O(R·C)1class Solution {
2 private int find(int[] parent, int x) {
3 while (parent[x] != x) {
4 parent[x] = parent[parent[x]];
5 x = parent[x];
6 }
7 return x;
8 }
9
10 public int floodLevel(int[][] elevation) {
11 int rows = elevation.length, cols = elevation[0].length;
12 int total = rows * cols;
13 Integer[] order = new Integer[total];
14 for (int i = 0; i < total; i++) order[i] = i;
15 Arrays.sort(order, (a, b) -> elevation[a / cols][a % cols] - elevation[b / cols][b % cols]);
16 int[] parent = new int[total];
17 boolean[] added = new boolean[total];
18 for (int i = 0; i < total; i++) parent[i] = i;
19 int[] dr = {1, -1, 0, 0};
20 int[] dc = {0, 0, 1, -1};
21 for (int id : order) {
22 int r = id / cols, c = id % cols;
23 added[id] = true;
24 for (int d = 0; d < 4; d++) {
25 int nr = r + dr[d], nc = c + dc[d];
26 if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && added[nr * cols + nc]) {
27 parent[find(parent, id)] = find(parent, nr * cols + nc);
28 }
29 }
30 if (added[0] && added[total - 1] && find(parent, 0) == find(parent, total - 1)) {
31 return elevation[r][c];
32 }
33 }
34 return 99;
35 }
36}