DEV Community

Shivam Seth
Shivam Seth

Posted on • Updated on

Water the plants complete solution with full logic in O(n), 28 days solution .(java)

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;

}
Enter fullscreen mode Exit fullscreen mode

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));
}
}

Discussion (0)