# Minimum Fountains

Posted: 24 Nov, 2020
Difficulty: Easy

## PROBLEM STATEMENT

#### Note:

``````1. 0-based indexing is used in the array.
2. We only care about the garden from 0 to 'N' only. So if i - 'ARR'['i'] < 0 or i + 'ARR'['i'] > 'N', you may ignore the exceeding area.
3. If some fountain covers the garden from position 'A' to position 'B', it means that the water from this fountain will spread to the whole line segment with endpoints 'A' and 'B'.
``````
##### Input Format:
``````The first line of the input contains an integer 'T', denoting the number of test cases.

The first line of each test case contains the integer 'N', denoting the size of the garden.

The second line of each test case contains 'N' + 1 space-separated integers denoting the array elements.
``````
##### Output Format:
``````For each test case, print a single integer that corresponds to the minimum number of fountains to be activated.
``````

#### Note :

``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= 'T' <= 50
1 <= 'N' <= 10^4
1 <= 'ARR'[i] <= 'N'

Where 'ARR[i]' represents the elements at 'i'th index.

Time Limit: 1 sec
``````
Approach 1
• For every fountain, we can try to find the pair area = (left, right), where left and right are the leftmost and the rightmost index respectively where the current fountain can reach.For every index 'I' = 0 to 'I' = 'N' -1, 'LEFT' = max(0, 'I' - 'ARR'['I']) and  'right' = min('I' + ('ARR'['I'] + 1), 'N').
• Now we can sort the array of pairs in non-decreasing order according to 'LEFT' to find the minimum number of fountains.
• Let us create a 'DP' array of size 'N' + 1 and initialise each index to 'N' + 1 because in worst that n+1 would be the minimum number of fountains that we have to turn on and let 'DP'[0] = 0 because to cover the 0 area no fountain is required
• For each of the intervals, we can use the following transition:
• For a particular index 'I' we have 2 options, either to start a new fountain or to use the previous fountain which can cover the current index.
• So we can use the following transition, For 'I' = 'AREA'[0] +1 to 'I' = 'AREA'[1] + 1, 'DP'[i] = min('DP'[i], 'DP'['AREA'[0] + 1]), where 'AREA'[0] represents the leftmost index where the current fountain can reach and 'AREA'[1] represents the rightmost index.
• After the loop ends, 'DP'['N'] will contain the minimum number of fountains.