#2105

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Watering Plants II

Simulate watering a row of plants with Alice and Bob using two-pointer scanning, tracking refills precisely for each step.

array two pointers simulation

Problem Statement

Alice and Bob are watering plants arranged in a row labeled from 0 to n - 1. Each plant requires a specific amount of water, and both start with full watering cans with capacities capacityA and capacityB. Alice waters from the left, Bob from the right, moving one plant at a time toward the center.

Given an array plants where plants[i] is the water needed for the ith plant, and integers capacityA and capacityB for Alice's and Bob's cans, return the total number of refills required to water all plants. If both reach the same plant, only one waters it, refilling if necessary.

Examples

Example 1

Input: plants = [2,2,3,3], capacityA = 5, capacityB = 5

Output: 1

Initially, Alice and Bob have 5 units of water each in their watering cans.
Alice waters plant 0, Bob waters plant 3.
Alice and Bob now have 3 units and 2 units of water respectively.
Alice has enough water for plant 1, so she waters it. Bob does not have enough water for plant 2, so he refills his can then waters it. So, the total number of times they have to refill to water all the plants is 0 + 0 + 1 + 0 = 1.

Example 2

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

Output: 2

Initially, Alice and Bob have 3 units and 4 units of water in their watering cans respectively.
Alice waters plant 0, Bob waters plant 3.
Alice and Bob now have 1 unit of water each, and need to water plants 1 and 2 respectively.
Since neither of them have enough water for their current plants, they refill their cans and then water the plants. So, the total number of times they have to refill to water all the plants is 0 + 1 + 1 + 0 = 2.

Example 3

Input: plants = [5], capacityA = 10, capacityB = 8

Output: 0

There is only one plant.
Alice's watering can has 10 units of water, whereas Bob's can has 8 units. Since Alice has more water in her can, she waters this plant. So, the total number of times they have to refill is 0.

Constraints

n == plants.length
1 <= n <= 105
1 <= plants[i] <= 106
max(plants[i]) <= capacityA, capacityB <= 109

Solution Approach

Two-pointer simulation

Initialize two pointers, left at 0 and right at n-1. Track Alice and Bob's remaining water. Move pointers toward the center, checking if the current plant exceeds available water. Refill as needed and increment the refill count.

Handle meeting point

If left and right pointers meet at the same plant, choose one to water it. Check if their remaining water is enough. Refill if necessary, ensuring only a single refill is counted for this shared plant.

Aggregate total refills

Sum all refill increments from both sides throughout the traversal. Return the final total refills as the output, which represents the minimum number of times either Alice or Bob had to refill while maintaining the two-pointer invariant.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) since each plant is visited once. Space complexity is O(1) as only pointers and counters are stored, no extra arrays.

What Interviewers Usually Probe

Expect a simulation using two pointers with careful refill tracking.
Check for edge cases when Alice and Bob meet on the same plant.
Observe how water capacities decrement and require refills in-place.

Common Pitfalls or Variants

Common pitfalls

Not counting refills correctly when both meet at the middle plant.
Incorrectly decrementing water for plants already watered.
Using extra space instead of simulating in-place, violating O(1) space expectation.

Follow-up variants

Watering plants with more than two people, each moving from different ends.
Varying refill costs per person, tracking weighted total refills.
Plants arranged in a circle, requiring wrap-around two-pointer simulation.

FAQ

How does the two-pointer pattern apply to Watering Plants II?

The two-pointer pattern lets Alice and Bob traverse from opposite ends simultaneously, tracking water left and refills efficiently.

What should I do when Alice and Bob meet at the same plant?

Only one person waters the plant, refilling if needed, and ensure the refill is counted once to maintain minimal total refills.

Can the array have a single plant?

Yes, if there is one plant, the person with enough water waters it, possibly requiring zero refills.

What is the time complexity of the simulation?

Time complexity is O(n) since each plant is considered exactly once with simple operations per step.

Does GhostInterview handle capacity edge cases?

Yes, it tracks Alice and Bob's remaining water accurately, ensuring correct refill counts for all capacity and plant combinations.

terminal

Solution

Solution 1: Two Pointers + Simulation

We use two variables $a$ and $b$ to represent the amount of water Alice and Bob have, initially $a = \textit{capacityA}$, $b = \textit{capacityB}$. Then we use two pointers $i$ and $j$ to point to the head and tail of the plant array, and simulate the process of Alice and Bob watering from both ends to the middle.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

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

Continue Practicing

#2109 adding spaces to a string #2149 rearrange array elements by sign #2161 partition array according to given pivot