Minimum Taps to Water the Whole Garden

Problem Statement

Minimum Taps to Water the Whole Garden There is a one-dimensional garden on the x-axis. The garden starts at the point 0 and ends at the point n (that is, the length of the garden is n ). There are n + 1 taps located at the points [0, 1, ..., n] in the garden. You are given an integer n and an integer array ranges of length n + 1 , where ranges[i] (0-indexed) means that the i -th tap can water the area [i - ranges[i], i + ranges[i]] if it is opened. Return the minimum number of taps that should be opened to water the whole garden. If the garden cannot be watered, return -1 . Input Format The first line contains a single integer n . The second line contains n + 1 space-separated integers ranges[0], ranges[1], ..., ranges[n] . Output Format Print a single integer — the minimum number of taps that have to be opened so that every point of the segment [0, n] is watered, or -1 if no set of taps waters the whole garden. Constraints 1 <= n <= 10000 (inferred — the source screenshot carri