PROBLEM OF THE DAY : 18/01/2024 | Water the plants

Welcome to the daily solving of our PROBLEM OF THE DAY with Yash Dwivedi We will discuss the entire problem step-by-step and work towards developing an optimized solution. This will not only help you brush up on your concepts of Greedy but also build up problem-solving skills.

In this problem, A gallery with plants is divided into n parts, numbered 0, 1, 2, 3, ..., n-1. There are provisions for attaching water sprinklers in every division. A sprinkler with range x at division i can water all divisions from i-x to i+x.

Given an array gallery[] consisting of n integers, where gallery[i] is the range of the sprinkler at partition i (a power of -1 indicates no sprinkler attached), return the minimum number of sprinklers that need to be turned on to water the entire gallery. If there is no possible way to water the full length using the given sprinklers, print -1.

Example :

Input:
n = 6
gallery[] = {-1, 2, 2, -1, 0, 0}
Output:
2

Explanation: 
Sprinklers at index 2 and 5can water the full gallery, span ofsprinkler at index 2 = [0,4] and spanof sprinkler at index 5 = [5,5].

Give the problem a try before going through the video. All the best!!!
Problem Link: https://www.geeksforgeeks.org/problems/water-the-plants--170646/1