FastPrep
Problem · Array

Minimum Number of Taps to Water a Garden

Learn this problem
● HardGoldman Sachs logoGoldman SachsFULLTIMEOA

Problem statement

A one-dimensional garden covers the closed interval [0, n]. Tap i waters [i - ranges[i], i + ranges[i]], clipped to the garden.

Return the minimum number of taps needed to water every point in [0, n]. Return -1 if complete coverage is impossible.

Function

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

Examples

Example 1

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

Tap 1 covers the whole interval [0,5].

Example 2

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

No tap covers a positive-length interval.

Constraints

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

More Goldman Sachs problems

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