Watering Plants II — Medium Problem & Solution

A row of plants needs watering. Alice starts at the left end with a can holding capacityA, Bob starts at the right end with capacityB.

Difficulty: Medium
Topics: Arrays, Two Pointers, Simulation
Asked at: Amazon, Google, Paytm
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A row of plants needs watering. Alice starts at the left end with a can holding capacityA, Bob starts at the right end with capacityB. They water simultaneously — Alice moves right, Bob moves left — and plant i needs exactly plants[i] units.

Before watering a plant, a gardener whose can holds less than the plant needs refills it completely (a refill is instantaneous). If both reach the same plant, the one with more water in the can waters it; on a tie Alice does.

Return the total number of refills.

Example 1

Input: plants = [2,2,3,3], capacityA = 5, capacityB = 5
Output: 1
Explanation: Alice waters 2 and 2 (1 left), Bob waters 3 then refills for the second 3.

Example 2

Input: plants = [2,2,3,3], capacityA = 3, capacityB = 4
Output: 2

Example 3

Input: plants = [5], capacityA = 10, capacityB = 8
Output: 0
Explanation: Alice has more water and can cover the single plant.

Constraints

1 <= plants.length <= 100000
1 <= plants[i] <= 1000000
max(plants[i]) <= capacityA, capacityB <= 1000000000

How to solve Watering Plants II

The two gardeners are independent until they meet, so a single loop advancing both pointers is a faithful simulation. Only the middle plant of an odd-length row needs the tie rule.

Approach

Keep i at the left, j at the right, and the two current can levels.
While i < j, water plants[i] with Alice and plants[j] with Bob, refilling first whenever the level is short.
If the pointers land on the same plant, refill once when neither can covers it — the one with more water tries.

Why it works

Refilling only when short is optimal because a refill always restores the can to full, so doing it earlier can never help and always costs one more. The problem guarantees every capacity is at least the largest plant, so one refill is always enough.

Complexity

Time — O(n)
Space — O(1)

Pitfalls

Refilling when the level merely equals the plant's need wastes a refill — the comparison is strict.
For the shared middle plant only max(a, b) matters; whoever it is, the count goes up by at most one.
Capacities reach 10^9, so the levels fit int but leave no headroom for intermediate sums.

Reference solution

Python

from typing import List

def minimumRefill(plants: List[int], capacityA: int, capacityB: int) -> int:
    i, j = 0, len(plants) - 1
    a, b = capacityA, capacityB
    refills = 0
    while i < j:
        if a < plants[i]:
            refills += 1
            a = capacityA
        a -= plants[i]
        i += 1
        if b < plants[j]:
            refills += 1
            b = capacityB
        b -= plants[j]
        j -= 1
    if i == j and max(a, b) < plants[i]:
        refills += 1
    return refills

JavaScript

var minimumRefill = function(plants, capacityA, capacityB) {
    var i = 0, j = plants.length - 1;
    var a = capacityA, b = capacityB, refills = 0;
    while (i < j) {
        if (a < plants[i]) { refills++; a = capacityA; }
        a -= plants[i]; i++;
        if (b < plants[j]) { refills++; b = capacityB; }
        b -= plants[j]; j--;
    }
    if (i === j && Math.max(a, b) < plants[i]) refills++;
    return refills;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue