7

Minimum Number Of Taps To Water Garden

Difficulty: HARD
Contributed By
Anish De |Level 1
Avg. time to solve
15 min
Success Rate
85%

Problem Statement

The gardener wants to water the garden by opening the minimum number of taps. The garden is one-dimensional along the x-axis of length N i.e. the garden starts from point 0 and ends at point N. There are N + 1 tap located at points [0, 1, 2, …, N] in the garden.

You are given an integer N, and an array named “ranges” of size N + 1(0-indexed). The ith tap, if opened, can water the gardener from point (i - ranges[i]) to (i + ranges[i]) including both. The task is to find the minimum number of taps that should be open to water the whole garden, return -1 if the garden can not be watered.

Example :

Watering The Garden

Follow Up:
Can you solve the problem in O(N) time?
Input Format:
The first line contains a single integer T representing the number of test cases. 

The first line of each test case will contain the integer N.

The second and the last line of each test case will contain N single space-separated integers representing the elements of the array “ranges”.
Output format :
For each test case, print a single integer representing the value of the minimum number of taps needed to open by the gardener to fill the whole garden.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 10^4
0 <= ranges[i] <= 100

Time Limit: 1 sec
Sample Input 1 :
2
3
0 0 0 0
7
1 2 1 0 2 1 0 1
Sample Output 1 :
-1
3
Explanation For Sample Input 1 :
In test case 1, the ranges of taps are as follows : [ [ 0, 0 ], [ 1, 1 ], [ 2, 2 ] ]. So in the worst case, if we open all the taps, then it’s impossible to fill the gaps i.e (0-1), (1,2), (2,3). So it’s impossible to fill the garden.

In test case 2, the ranges of taps are as follows : [ [ -1, 1 ],[ -1, 3 ],[ 1, 3 ],[ 3, 3 ],[ 2, 6 ],[ 4, 6 ],[ 6, 6 ],[ 6, 8 ] ]. To fill the garden i.e [ 0, 7 ] , the gardener needs to open a minimum of three taps i.e. tap 2: [ -1, 3 ] , tap 5: [ 2, 6 ], tap 8: [ 6, 8 ] to fill the whole garden.
Sample Input 2 :
2
8
4 0 0 0 0 0 0 0 4
8
4 0 0 0 4 0 0 0 4
Sample Output 2 :
2
1
Reset Code
Full screen
copy-code
Console