Fewest Sprinklers to Cover the Whole Path
Solve this ProblemA garden path runs along a line from position 0 to position n, with a sprinkler at every whole-number position 0, 1, …, n. The sprinkler at position i can water everything within ranges[i] of itself. Every point on the path from 0 to n must be watered. Find the fewest sprinklers to switch on, or −1 if no selection can water the entire path.
Trying every set of sprinklers is exponential. But watering the path with as few overlapping stretches as possible is the same as reaching position n with as few "hops" as possible, where each sprinkler is a hop that starts at its left edge. That makes the jump-window greedy work.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ n ≤ 10 and ranges.length = n + 1; a garden path runs along the x-axis from 0 to n, with a sprinkler at every integer position 0, 1, …, n - ◆
0 ≤ ranges[i] ≤ 5; the sprinkler at position i waters everything from i − ranges[i] to i + ranges[i] - ◆
Turn on any set of sprinklers. Every point from 0 to n must be watered; two watered stretches that merely touch at a point (for example [0, 3] and [3, 6]) still leave no gap - ◆
Return the fewest sprinklers that water the whole path, or −1 if it is impossible
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Try Every Set of Sprinklers and Check for Dry Gaps
BruteTry every subset of the n + 1 sprinklers (a bitmask). For each subset, walk along the path one unit segment at a time — [0, 1], [1, 2], … , [n − 1, n] — and check that some chosen sprinkler's watered range contains the whole segment. If every segment is covered, the subset is valid; keep the smallest valid subset's size, or −1 if none is valid. Correct by exhaustion, but there are 2ⁿ⁺¹ subsets and each needs a full n × n check.
O(2ⁿ · n²)O(1)1class Solution {
2 public int fewestSprinklers(int n, int[] ranges) {
3 int count = ranges.length;
4 int best = -1;
5 for (int mask = 1; mask < (1 << count); mask++) {
6 boolean coversAll = true;
7 for (int x = 0; x < n && coversAll; x++) {
8 boolean covered = false;
9 for (int s = 0; s < count; s++) {
10 if ((mask & (1 << s)) != 0 && s - ranges[s] <= x && s + ranges[s] >= x + 1) {
11 covered = true;
12 break;
13 }
14 }
15 if (!covered) coversAll = false;
16 }
17 if (coversAll) {
18 int used = Integer.bitCount(mask);
19 if (best == -1 || used < best) best = used;
20 }
21 }
22 return best;
23 }
24}Optimal — Turn It Into "Fewest Hops" With a Reach Table
OptimalPrecompute reach[l]: the farthest right end of any sprinkler whose watered range begins at l (clipping ranges to [0, n]). Covering [0, n] with as few ranges as possible is now the same as reaching position n with as few hops as possible, where a "hop" from anywhere in the current window can land as far as the best reach seen. Scan positions left to right, tracking the farthest reachable end; whenever the scan hits the end of the current window, a new sprinkler is needed — if the farthest end has not moved past the current position there is a dry gap and the answer is −1; otherwise use one more sprinkler and extend the window to the farthest end.
O(n)O(n)1class Solution {
2 public int fewestSprinklers(int n, int[] ranges) {
3 int[] reach = new int[n + 1];
4 for (int i = 0; i <= n; i++) {
5 int left = Math.max(0, i - ranges[i]);
6 int right = Math.min(n, i + ranges[i]);
7 reach[left] = Math.max(reach[left], right);
8 }
9 int used = 0, currentEnd = 0, farthest = 0;
10 for (int pos = 0; pos < n; pos++) {
11 farthest = Math.max(farthest, reach[pos]);
12 if (pos == currentEnd) {
13 if (farthest <= pos) return -1;
14 used++;
15 currentEnd = farthest;
16 }
17 }
18 return used;
19 }
20}