Minimum Number of Taps to Open to Water a Garden

Introduction

Today’s problem, i.e., –“Minimum Number of Taps to Open to Water a Garden,” is highly asked in product-based companies like Amazon, Google, and Microsoft.

We’ll go over all the methods, including brute force and the most efficient way to solve this problem.

We are going to solve this problem by a different approach.

Problem Statement

There is a one-dimensional garden on the x-axis. The garden starts at point 0 and ends at point n. There are n+1 taps located in the garden. Given an integer n and an integer array ranges of length n+1 where range[i] (0-indexed) means the ith tap can water the area [i-ranges[i],i+ranges[i]] if it was open. Return the minimum no of taps to water the whole garden. Else, return -1.

Eg: N=5 and ranges=[3 , 4, 1, 1, 0, 0]

Output : 1.

Explanation of Problem Statement

In this problem, the coordinate axis system is represented in the form of taps location along with the x-axis, and the number of points of the locator is of size n+1. The number of locators as index starts from 0 to n, so the total taps present is n+1 in the garden. We have an N length size garden in which the locator of n+1 taps, with the range value of each tap its location, starts with 0 for 1 and moves till n for n+1. Each tap tends to water the range over its position in to and fro manner in i+range[i] to i-range[i]. So Here we have to find the minimum number of taps required by which we can water the whole garden area.

Let’s understand the problem by taking an example:-

In a very brute-force manner understanding the problem.

Let's take the value length of garden=N and the range of size N+1, for N+1 taps in the garden, covering the to and fro direction value for range same in i+range[i] and same in i-range[i] at the same time.

Eg: N=5 and ranges[N+1=6]= { 3, 4, 1, 1, 0, 0}.

Source:- Minimum Number of Taps to Open to Water a Garden

Index : 0 1 2 3 4 5

Ranges: 3 4 1 1 0 0

X---------------------------------------------------X

(0 index range is 3 so 0-3 and 0+3 i.e -3 to 3)

X-------------------------------------------------------------------X

(1 index range is 4 so 1-4 and 1+4 i.e -3 to 5, covers the whole area)

X----------------X

(2 index range is 1 so 2-1 and 2+1 i.e 1 to 3)

X-------------X

(3 index range is 1 so 3-1 and 3+1 i.e 2 to 4)

(4 index range is o so 4-0 and 4+0 i.e 4 to 4)

(5 index range is 0 so 5-0 and 5+0 i.e. 5 to 5)

min(0)---------------------------------max(5)

-3 5(Range )

The approach is Like that for the first time, find all the ranges, and then the next part finds the number of the taps which are going to fit with minimal for watering over the garden.

Indices at location 1, tap has the range value of 4, which covers the entire garden range from coordinate point -3 to 5, to water it so the minimum tap required for it is just 1 Tap, Tap present at index 1 with range =4 water the whole garden.

Solution-1

Now we are going to solve the problem, using the brute force manner approach, as previously discussed, and taking the approach we are first taking the find for range value finding, to make it suited to insert in range of length of the garden covered.

Algorithm for the Brute-Force Approach

Define min and max value as zero initially.
Now iterate under loop condition till any chance for watering the garden till the length of the garden max<n.
Now, as for the value of the given range in the ranges array, we can commute the min and max range for each tap locator which gets added to water the garden, using the second loop with the if condition for updating the upper level, as minimum part not going to less than 0.
After that update of max=i+ranges[i], then checking things if we reached the end of the garden, and no max value found remains the same as min then, return -1.
After each iteration of the N size length of the garden, more than 1 tap is required, then we set min =max, and before that increment the tap as one is utilized as well.
We ran in the loop till we reached the max value end of the garden length.
Return the no of taps required to water the garden.

Code for the Brute-Force

class Solution {
  public int minTaps(int n, int[] ranges) {
  int min=0,max=0,tap=0;
  while(max<n){
  for(int i=0;i<ranges.length;i++){
  if(i-ranges[i]<=min && i+ranges[i]>max)
max=i+ranges[i];
}
  if(min==max) return -1;
tap++;
min=max;
}
  return tap;
}
}

Input:

n = 7, ranges = [1,2,1,0,2,1,0,1]

Output:

We need to write the driver code to run the code; it’s a functional requirement code snippet for the logic implementation.

Complexity for the Brute-Force:

Talking about the Time Complexity, we run the outer loop over the length of the garden, i.e., N, and under we are running the for loop to find new ranges to water the remaining part of the garden in which we are doing the ranges. Length iteration every time i.e. N+1 so in general Time complexity of the Brute-Force Approach is likely to be N*(N+1) i.e., O(N^2).

Talking about Space Complexity, we just use the variable of data type int and store the value by overwriting it for further use, which seems to be in O(constant), which implies O(1).

Now, seeing the Coding part iteration, we start from the index =0 every time we see it in the loop.

for(int i=0;i<ranges.length;i++){
if(i-ranges[i]<=min && i+ranges[i]>max)
max=i+ranges[i];
}

To reduce the time to run the code, we reduce some repetition by using extra variables to keep track of the part of the garden which is watered and, for next time, starts for the next step ahead of the watered part.

class Solution {
  public int minTaps(int n, int[] ranges) {
  int min=0,max=0,tap=0,idx=0;
  while(max<n){
  for(int i=idx;i<ranges.length;i++){
  if(i-ranges[i]<=min && i+ranges[i]>max)
{
max=i+ranges[i];
idx=i;
}
}
  if(min==max) return -1;
tap++;
min=max;
}
  return tap;
}

Input:

n = 7, ranges = [1,2,1,0,2,1,0,1]

Output:

Time Complexity: Here below, the use of idx helps to keep track of it Time Complexity is O(N*N)~O(N^2)

Space Complexity: Space Complexity is also O(1); it’s just some internal repetition stop for reiteration.

Solution-2

In this solution, we use the concept of Dynamic Programming to reduce the Time Complexity to O(N). First, let me explain why dp is very suitable for this problem. The idea is this: if we know the min number of taps to water from 0 to i, we can use this to extrapolate the min number of taps to water from 1 to i+j. Ok, let me explain what I mean by this. So we loop through every tap, which is represented by the ranges array. Since the tap spouts water in the left and right directions, it can water the garden from [left, right]. Of course, the garden's limit should be considered; we can't water a negative length, nor can we water outside the garden length. If we know the min number of taps needed to water from 0 to the left, then it's easy to see that we can water the garden from left to right using the minimum number of taps to water until left + 1 since we use the current tap. We initialize dp[0] = 0 since no taps are needed to water a garden with 0 length.dp is effective in storing previously known results and building up from these previously known results. In this case, we want to store the min number of taps to water up from 0 to i where i < n. There, we broke down the requirement to get the min number of taps to water up from 0 to n to simpler subproblems. The first one is to water up to a 0 length and build up incrementally to n.

Algorithm for the DP

Declare a dp array of size n+2.
We initialize dp[0] = 0 since no taps are needed to water a garden with 0 lengths.
We find the min and max range value stored in variables in O(N).
DP is effective in storing previously known results and building up from these previously known results.
We store the min number of taps to water up from 0 to i where i < n.
We broke down the requirement to get the min number of taps to water up from 0 to n to simpler subproblems. The first one is to water up to a 0 length and build up incrementally to n.
At last, after computation, we check for dp[n] ==n+2, then we reach the end of dp array we failed so return -1 else return dp[n], which contains the minimum tap to water the garden.

Code for the DP

class Solution {
public int minTaps(int n, int[] ranges) {
  int[] dp = new int[n+1];
Arrays.fill(dp,n+2);
dp[0] = 0;
  for(int i=0;i<=n;i++) {
  int min = Math.max(0,i-ranges[i]);
  int max = Math.min(n,i+ranges[i]);
  for(int j=min+1;j<=max;j++) {
dp[j] = Math.min(dp[j],dp[min]+1);
}
}
  return dp[n] == n+2 ? -1 : dp[n];
}
}

Input:

n = 7, ranges = [1,2,1,0,2,1,0,1]

Output:

Time Complexity: is O(N).

Space Complexity: is O(N).