Minimum Number of Taps to Water the Garden

Given a garden that extends along a one-dimensional x-axis from point 0 to point N, your task is to determine the minimum number of taps needed to water the entire garden. The garden has N+1 taps located at positions [0, 1, 2, ..., N].

Each tap, once opened, waters a range from (i - ranges[i]) to (i + ranges[i]), inclusive. You must find the fewest number of taps required to water every part of the garden from point 0 to point N. Return -1 if it's not possible to water the entire garden.

Input:

Integer T, the number of test cases 
For each test case:
- Integer N, the range of the garden.
- Array ranges of size N+1, where ranges[i] indicates the water coverage radius a tap at point i can achieve.

Output:

For each test case, a single integer representing the minimum number of taps required. If the garden cannot be fully watered, return -1.

Example:

Consider an input where T = 1, N = 5, and ranges = [3,4,1,1,0,0].

Input:
T = 1
N = 5
ranges = [3, 4, 1, 1, 0, 0]
Output:
1
Explanation:

By opening the tap at position 1, which covers points from -3 to 5, the entire garden from 0 to 5 is watered.

Constraints:

  • 1 <= T <= 10
  • 1 <= N <= 104
  • 0 <= ranges[i] <= 100
  • Time Limit: 1 sec
AnswerBot
2d

Find the minimum number of taps needed to water the entire garden with given tap ranges.

  • Iterate over each tap and find the maximum range it can cover.

  • Sort the taps based on their starting point and en...read more

Help your peers!
Add answer anonymously...
BNY Software Developer Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter