Find minimum no. of fountains needed

Question

There is a linear garden from 1 to n. At each point there is a fountain. Given array a[n]tells info about fountain such that its range is max(i-a[i],1) to the left of fountain to min(i+a[i],n) to the right of fountain. Find minimum no. of fountains needed to be activated so that whole garden is covered. e.g.if n=3 and a={1,2,1} then second fountain has range 1 to 3. So only 1 fountain needed. Here fountain at 1 has range of 1 to 2, fountain at 2 has range of 1 to 3 and fountain at 3 has range of 2 to 3 So only fountain 2 is enough to be activated to cover the whole garden.

Answer 1

Traverse through all the fountains and construct array jumps:

jumps[i] = {max range of all the fountains having their range's left boundary at i}

for (int i = 1; i <= n; i++){
l = max(1, i - arr[i-1])
r = min(n, i + arr[i-1])
jumps[l] = max(jumps[l], r - l);
}

Then apply Jump Game II (https://leetcode.com/problems/jump-game-ii/) on jumps array. This takes O(n) time