Daily bit(e) of C++ | Watering the garden
Daily bit(e) of C++ #317, Common interview problem: Watering the garden.
Today, we will look at a common C++ interview problem: Watering the garden.
Given a garden as the interval [0,n], determine the minimum number of sprinklers that need to be activated to water the garden.
Each index 0..n has a sprinkler which waters the range: [i-rng[i],i+rng[i]].
Note: two sprinklers {0,0} do not water the range [0,1] only [0,0] and [1,1].
For example, for the input {0,3,0,0,2,0,4,0}, the result is two, using the sprinklers at index 1 and 6.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/bPKcxTPPe.
Solution
We can translate this problem into a reachability problem.
Consider that a sprinkler at index i with range r allows us to jump from any index in the range [i-r, i+r] to i+r. The question then is how many jumps we need to reach from index 0 to index n.
To efficiently answer this question, we need to pre-process our data. At the left-most index reachable by a sprinkler, we store the rightmost index reachable by this sprinkler. This way, we know the furthest reachable index once we traverse this information.
With that, we only have to traverse this preprocessed array, keeping track of how many sprinklers we have used.
