Fewest Fountains to Water the Garden
Updated
Problem statement
A garden has n positions, numbered 1 to n, with one fountain at each position. The array locations has length n, and locations[i - 1] is the reach of the fountain at position i.
When the fountain at position i is turned on, it waters every position from max(i - locations[i - 1], 1) to min(i + locations[i - 1], n), including both ends.
All fountains start turned off. Return the smallest number of fountains you must turn on so that every position from 1 to n is watered.
Positions are whole spots. Two ranges that end and start at neighboring positions, such as 1 to 2 and 3 to 5, together water every position from 1 to 5.
Function
fountainActivation(locations: int[]) → intExamples
Example 1
locations = [1,0,0,1,0]return = 2The fountain at position 1 waters positions 1 to 2. The fountain at position 4 waters positions 3 to 5.
Together they water every position, so 2 fountains are enough. No single fountain waters all five positions, so 1 is not enough.
Example 2
locations = [0,0,1,0,0,0]return = 4Only the fountain at position 3 waters more than its own position: it waters positions 2 to 4.
Positions 1, 5 and 6 can only be watered by their own fountains, since every other reach is 0. So turn on fountains 1, 3, 5 and 6: the answer is 4.
Example 3
locations = [2,0,5]return = 1The fountain at position 3 has reach 5. Its range is max(3 - 5, 1) = 1 to min(3 + 5, 3) = 3, the whole garden. One fountain is enough.
Constraints
1 <= locations.length <= 10000 <= locations[i] <= 1000
More DocuSign Online Assessment questions
- Max Sum With No Two Adjacent PicksOA · Seen Apr 2026
- Max Sum With No Two Adjacent Picks on a CircleOA · Seen Apr 2026
- Beautiful Number OrderingsOA · Seen Feb 2026
- Grid Path With the Most ClearanceOA · Seen May 2025
- Vehicle Mixes for a Wheel TotalOA · Seen May 2025
- Count Sales Rung Up at the Wrong PriceOA · Seen Feb 2021
- Most Disjoint Intervals From Starts and DurationsOA · Seen Feb 2021
- Lowest Start That Keeps Running Totals PositiveOA · Seen Feb 2021
- Fewest Student Groups Within a Level GapOA · Seen Nov 2020
- Alphabetize a Word ListOA · Seen May 2020
Similar questions at other companies
- Maximum Compatible Time WindowsIBM · OAIBM interview questions
- Maximum Even-Sum Neighboring PairsDRW · OADRW interview questions
- Minimize Total Input Cost (for LTMS)Salesforce · OASalesforce interview questions
- Maximize Protected City PopulationAmazon · OA
- Minimum Markers to Clear Line SegmentsHSBC · OAHSBC interview questions
- Minimum Machines for TasksExpedia · OAExpedia interview questions
- Network FormationPalantir · OAPalantir interview questions
- Maximum Even-Sum Adjacent Pairs in a Circular ArrayTesla · OATesla interview questions
- University Career FairRoblox · OARoblox interview questions
- Minimum Jumps to Reach the EndNutanix · OANutanix interview questions