Water the plants complete solution with full logic in O(n), 28 days solution of GFG.(java)
input = [2,3,4,-1,2,0,0,-1,0]
output [-1]
input = [-1,-1,2,2,0,0]
//code
import java.util.*;
class ONE {
int min_sp(int gal[], int n)
{
int arr[] = new int [n];
Arrays.fill(arr, -1);
for (int i=0;i<n;++i)
{
// System.out.println("its n "+n);
if (gal[i]==0)
{
// System.out.println("its arr[i] "+arr[i]);
arr[i]=Math.max(arr[i],i);
continue;
}
if (gal[i]!=-1)
{
int k=i+gal[i];
// System.out.println("its k "+k);
// int j=max (0,i-gal[i]);
int j=Math.max(0,i-gal[i]);
// System.out.println("its j "+j);
for(int sp = j;sp<=Math.min(n,k);++sp)
{if(sp==n)
continue;
arr[sp]=Math.max(k,arr[sp]);}
}
}
int c =0,i=0;
while(i<n)
{
// System.out.println("its i and n "+i+" "+n);
// System.out.println("its i and n "+i+" "+arr[i]);
if (i==-1||arr[i]==-1)
return -1;
++c;
i=arr[i]+1;
}
return c;
}
public static void main(String[] arr)
{
// Scanner in = new Scanner(System.in);
int gal[] ={2,3,4,-1,2,0,0,-1,0};
ONE s = new ONE();
int n=gal.length;
System.out.print(s.min_sp(gal,n));
}
}
Top comments (0)