Watering Plants II

Medium
772.

Watering Plants II

Watering Plants II is a medium coding problem on arrays, two pointers and simulation, asked in Amazon, Google and Paytm interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} plants
 * @param {number} capacityA
 * @param {number} capacityB
 * @return {number}
 */
var minimumRefill = function(plants, capacityA, capacityB) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Watering Plants II — Solution in Python, Java & C++

Watering Plants II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Watering Plants II is a medium coding problem on arrays, two pointers and simulation, asked in Amazon, Google and Paytm interviews.

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

Hints for Watering Plants II

  1. Hint 1

    Alice and Bob never interfere before they meet, so simulate both pointers in lockstep.

  2. Hint 2

    A refill is forced exactly when the remaining water is less than what the next plant needs.

  3. Hint 3

    The odd-length case leaves one plant for whoever holds more water.

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

  1. Keep i at the left, j at the right, and the two current can levels.
  2. While i < j, water plants[i] with Alice and plants[j] with Bob, refilling first whenever the level is short.
  3. 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

Java

public static int minimumRefill(int[] plants, int capacityA, int capacityB) {
    int i = 0, j = plants.length - 1;
    int 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;
}

C++

int minimumRefill(vector<int>& plants, int capacityA, int capacityB) {
    int i = 0, j = (int) plants.size() - 1;
    int 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 && max(a, b) < plants[i]) refills++;
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Two Pointers Technique