How should I practice Minimum Taps to Water a Garden?

Start by reading the full statement, solve the visible examples, then compare the pattern against related The D.E. Shaw Group onsite interview problems in FastPrep.

Is Minimum Taps to Water a Garden associated with The D.E. Shaw Group?

FastPrep tags this as a The D.E. Shaw Group onsite interview coding practice problem when the problem catalog has that company and stage context.

Minimum Taps to Water a Garden

The D.E. Shaw Group● HardFULLTIMEONSITE INTERVIEW

Problem statement

A straight garden occupies the entire real interval [0, n]. There is a tap at every integer position from 0 through n, inclusive.

Tap i has radius ranges[i]. When opened, it waters the closed interval [i - ranges[i], i + ranges[i]]. Water outside the garden is harmless, and intervals that touch at an endpoint leave no gap.

Return the minimum number of taps needed to water every point of the garden. Return -1 if that is impossible.

Function

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

Examples

Example 1

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

Tap 1 waters [-3,5], which contains the entire garden [0,5]. At least one tap is necessary because the garden has positive length, so one is optimal.

Example 2

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

Each tap waters only its own point. Points between consecutive taps remain dry even if every tap is opened, so full coverage is impossible.

Constraints

1 <= n <= 10^4.
ranges.length == n + 1.
0 <= ranges[i] <= 100.

More The D.E. Shaw Group problems

See The D.E. Shaw Group hiring insights