Watering Plants II — Editorial

Opening the reading…

Intuitionwhy the two ends can be simulated independently

Alice's next plant is always the leftmost unwatered plant, while Bob's next plant is always the rightmost unwatered plant. That means the entire unfinished garden is described by two indices, i and j. Each gardener only needs their current water and the number of refills so far; no earlier plant can affect which plant they choose next.

As long as i is smaller than j, the gardeners water different plants, so their actions are independent and can be simulated one after the other. When i equals j, both have reached the same plant. You must not let both water it: compare their remaining water, give the plant to Alice on a tie, and count at most one refill for that final plant.

Approach

Set i to the left end and j to the right end, and start both current-water values at their full capacities, because each gardener begins with a full can and those values describe the state needed for every later decision.

While i is at most j, first check whether the pointers meet, because the common plant must be assigned to exactly one gardener rather than processed once from each side.

If i equals j, choose Alice when curA is at least curB and choose Bob otherwise, because the statement gives Alice the tie. Refill the chosen can only when it lacks enough water, water the plant, and stop the loop because no plant remains.

When i is smaller than j, refill Alice's can if curA is less than plants[i], subtract that plant's water, and increment i; the strict comparison avoids counting a refill when the can has exactly enough water.

Process Bob's right plant in the same way using curB and plants[j], then decrement j, because Bob's state is independent while the pointers refer to different plants.

Return the combined refill count after the pointers cross or the meeting plant is handled, because every plant has then been watered exactly once.

Complexityone visit per plant and constant working state

MEASURE	BOUND	WHY
Time	O(n)	Each loop iteration removes two different plants, except for one final iteration that handles the meeting plant. Thus every plant is inspected and subtracted from a can exactly once, with no plant revisited after its pointer moves past it.
Space	O(1) extra	The algorithm stores only two indices, two current-water values, and the refill counter. The input array is not extra storage, and no output collection is created; the bound stays constant even when one gardener reaches the other end much earlier.

Here n is the number of plants.

Annotated solutionC++ · two pointers · explicit handling for the meeting plant

CPPSimulate both gardeners inward, then assign the single meeting plant to the gardener with more water remaining.

#include <vector>
using namespace std;

class Solution {
public:
    int minimumRefill(vector<int>& plants, int capacityA, int capacityB) {
        int n = plants.size();
        int i = 0;
        int j = n - 1;
        int curA = capacityA;
        int curB = capacityB;
        int refills = 0;

        while (i <= j) {
            if (i == j) {
                if (curA >= curB) {
                    if (curA < plants[i]) {
                        refills++;
                        curA = capacityA;
                    }
                    curA -= plants[i];
                } else {
                    if (curB < plants[i]) {
                        refills++;
                        curB = capacityB;
                    }
                    curB -= plants[i];
                }
                break;
            }

            if (curA < plants[i]) {
                refills++;
                curA = capacityA;
            }
            curA -= plants[i];
            i++;

            if (curB < plants[j]) {
                refills++;
                curB = capacityB;
            }
            curB -= plants[j];
            j--;
        }

        return refills;
    }
};

The i == j branch is deliberately before the ordinary left-and-right work. In that branch, comparing curA and curB decides who is allowed to water, and the chosen gardener may need one refill. The break prevents the same plant from entering either side of the normal simulation, so the meeting rule is applied once and only once.