FastPrepMinimum Number of Taps to Water a Garden
Problem · Array

Minimum Number of Taps to Water a Garden

Learn this problem
● HardFlexTrade logoFlexTradeFULLTIMEOA

Problem statement

A one-dimensional garden covers the interval from 0 through n. There are n + 1 taps, numbered from 0 through n.

Tap i waters the interval from max(0, i - ranges[i]) through min(n, i + ranges[i]).

Return the minimum number of taps that must be opened to water the entire garden. Return -1 if full coverage is impossible.

Function

minTaps(n: int, ranges: int[]) → int

Examples

Example 1

n = 5ranges = [3,4,1,1,0,0]return = 1

Opening tap 1 waters from 0 through 5, covering the whole garden.

Example 2

n = 3ranges = [0,0,0,0]return = -1

No tap covers a positive-length interval, so the garden cannot be fully watered.

Example 3

n = 7ranges = [1,2,1,0,2,1,0,1]return = 3

Three suitably chosen tap intervals cover every point from 0 through 7; no pair reaches the full interval.

Constraints

  • 1 <= n <= 10000
  • ranges.length == n + 1
  • 0 <= ranges[i] <= n

More FlexTrade problems

drafts saved locally
public int minTaps(int n, int[] ranges) {
  // Write your code here.
}
n5
ranges[3,4,1,1,0,0]
expected1
checking account