What is the brute force approach and complexity for Minimum Number of Taps to Open to Water a Garden?

Turn taps into intervals, then try opening or skipping each one with time complexity O(2^N) and space complexity O(N).

What is the optimal approach and complexity for Minimum Number of Taps to Open to Water a Garden?

maxReach[l] = farthest end of a tap starting at l; then jump greedily to the farthest reach with optimal time complexity O(N) and space complexity O(N).

How do you identify the pattern for Minimum Number of Taps to Open to Water a Garden?

Look for key signals in the prompt: "tap i waters [i − ranges[i], i + ranges[i]]" indicates Each tap is an interval. Turn the input into intervals first.; "water the whole garden" indicates Cover a whole range with no gaps → Video Stitching.; "minimum number of taps, or −1" indicates Fewest jumps, and detect a gap where the reach stops growing..

Minimum Number of Taps to Open to Water a Garden

Hard·LeetCode #1326 Pro OnlyTricky / Edge Case

LeetCode

Problem Statement

A garden lies along the x-axis from point 0 to point n, so its length is n. There are n + 1 taps, one at every whole point 0, 1, …, n.

Tap i, when opened, waters everything from i − ranges[i] to i + ranges[i].

Return the fewest taps you need to open so that the whole garden [0, n] is watered. If that's impossible, return -1.

Input

An integer n and an array ranges of length n + 1.

Output

One integer: the minimum number of taps, or -1.

Example 1

Input: n = 5, ranges = [3, 4, 1, 1, 0, 0]

Output: 1

Tap 1 waters [−3, 5], which covers the whole garden [0, 5] on its own.

Example 2

Input: n = 3, ranges = [0, 0, 0, 0]

Output: -1

Every tap waters only its own point. The ground between the points stays dry.

Constraints

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

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“tap i waters [i − ranges[i], i + ranges[i]]”

→ Each tap is an interval. Turn the input into intervals first.

“water the whole garden”

→ Cover a whole range with no gaps → Video Stitching.

“minimum number of taps, or −1”

→ Fewest jumps, and detect a gap where the reach stops growing.

Approach Complexity Ladder

Brute Force — try every set of tapsO(2^N)O(N)

Turn taps into intervals, then try opening or skipping each one

Better — DP over garden pointsO(N log N + N · R)O(N)

dp[x] = fewest taps watering [0, x]; each tap updates the points it covers

Optimal — maxReach array + Jump Game IIO(N)O(N)

maxReach[l] = farthest end of a tap starting at l; then jump greedily to the farthest reach

Brute Force Intuition

Turn each tap into the interval [max(0, i − r), min(n, i + r)] and sort by left end. Try every open / closed choice. A tap can be opened only if it starts inside the part already watered, since later taps start even further right. Record the fewest taps that reach n.

Recognition rule for this sub-pattern:

Pick or remove intervals to optimise coverage. Sorting by end and keeping the earliest finisher leaves the most room.

Remember this · Intervals

Trigger

Input is [start, end] pairs; overlap, merge, insert, meeting rooms, free time, minimum removals.

Think

After sorting, do I only ever need to compare against the most recent interval?

Key question

Sort by start or by end — which one makes the greedy choice obvious?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Intervals translate into production architectures and low-level memory mechanics.

LLD Architecture