Laying a Pipe Over Uneven Ground
Solve this ProblemA water pipe has to be laid over uneven ground described by a grid of heights, from the pump at the top-left cell to the tank at the bottom-right cell, moving between side-neighbouring cells. The strain of a route is the largest height difference between two consecutive cells on it. Find the smallest possible strain.
If steps up to some limit are allowed, deciding whether the destination is reachable is an ordinary flood fill. Because a larger limit never hurts, the smallest workable limit can be found by binary search.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ rows, cols ≤ 8; 0 ≤ heights[r][c] ≤ 99 - ◆
A pipe starts at the pump on the top-left cell and must end at the tank on the bottom-right cell, passing from each cell to a side-neighbouring cell (up, down, left or right) - ◆
The strain of a pipe route is the LARGEST absolute height difference between two consecutive cells on it - ◆
Return the smallest possible strain over all pipe routes (0 for a single cell)
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Keep Improving the Best Strain of Every Cell
BruteKeep for every cell the smallest strain found so far for reaching it (infinity at first, 0 for the start). Sweep over the whole grid again and again: from a cell with a known strain, extending the pipe to a neighbour gives strain max(strain so far, height difference of this step); keep it if it is lower. Stop when a whole sweep changes nothing; the answer is the value at the destination. Values can flow against the scan order, so many sweeps may be needed: O((R·C)²).
O((R·C)²)O(R·C)1class Solution {
2 public int gentlestPipe(int[][] heights) {
3 int rows = heights.length, cols = heights[0].length;
4 int[] dr = {1, -1, 0, 0};
5 int[] dc = {0, 0, 1, -1};
6 int INF = Integer.MAX_VALUE;
7 int[][] strain = new int[rows][cols];
8 for (int[] row : strain) Arrays.fill(row, INF);
9 strain[0][0] = 0;
10 boolean changed = true;
11 while (changed) {
12 changed = false;
13 for (int r = 0; r < rows; r++) {
14 for (int c = 0; c < cols; c++) {
15 if (strain[r][c] == INF) continue;
16 for (int d = 0; d < 4; d++) {
17 int nr = r + dr[d], nc = c + dc[d];
18 if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
19 int candidate = Math.max(strain[r][c], Math.abs(heights[r][c] - heights[nr][nc]));
20 if (candidate < strain[nr][nc]) {
21 strain[nr][nc] = candidate;
22 changed = true;
23 }
24 }
25 }
26 }
27 }
28 return strain[rows - 1][cols - 1];
29 }
30}Optimal — Binary Search on the Strain, Check With Breadth-First Search
OptimalSuppose we allow steps of height difference at most L. Then the question "can we get from the start to the destination?" is a plain reachability question, answered with a breadth-first search over allowed steps. If it is possible for L it is also possible for every larger L, so the possible answers are monotone: binary search the smallest L (between 0 and the maximum height 100) for which the search succeeds. About log₂(100) ≈ 7 searches of O(R·C) each.
O(R·C · log H)O(R·C)1class Solution {
2 private boolean canCross(int[][] heights, int limit) {
3 int rows = heights.length, cols = heights[0].length;
4 int[] dr = {1, -1, 0, 0};
5 int[] dc = {0, 0, 1, -1};
6 boolean[][] seen = new boolean[rows][cols];
7 Deque<int[]> queue = new ArrayDeque<>();
8 seen[0][0] = true;
9 queue.add(new int[]{0, 0});
10 while (!queue.isEmpty()) {
11 int[] cell = queue.poll();
12 for (int d = 0; d < 4; d++) {
13 int nr = cell[0] + dr[d], nc = cell[1] + dc[d];
14 if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || seen[nr][nc]) continue;
15 if (Math.abs(heights[nr][nc] - heights[cell[0]][cell[1]]) <= limit) {
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 gentlestPipe(int[][] heights) {
25 int lo = 0, hi = 100;
26 while (lo < hi) {
27 int mid = (lo + hi) / 2;
28 if (canCross(heights, mid)) {
29 hi = mid;
30 } else {
31 lo = mid + 1;
32 }
33 }
34 return lo;
35 }
36}