Problem Description

Alice and Bob need to water n plants arranged in a row, numbered from 0 to n - 1. Each plant requires a specific amount of water given in the array plants[i].

Initial Setup:

• Alice starts with a full watering can of capacity capacityA
• Bob starts with a full watering can of capacity capacityB

Watering Rules:

• Alice waters plants from left to right (starting at plant 0)
• Bob waters plants from right to left (starting at plant n-1)
• They water simultaneously and move at the same pace
• A person must water a plant if they have enough water in their can
• If they don't have enough water, they refill first (instantaneously), then water the plant
• When both meet at the same plant:
  • The person with more water in their can waters it
  • If they have equal amounts, Alice waters it

Goal: Find the minimum total number of refills needed by both Alice and Bob to water all plants.

Example: If plants = [2, 2, 3, 3], capacityA = 5, capacityB = 5:

• Alice waters plant 0 (needs 2), has 3 left
• Bob waters plant 3 (needs 3), has 2 left
• Alice waters plant 1 (needs 2), has 1 left
• Bob waters plant 2 (needs 3), but only has 2, so refills first (1 refill), then waters
• Total refills: 1

Intuition

Since Alice and Bob water plants from opposite ends moving toward each other, this naturally suggests a two-pointer approach. We can use pointer i for Alice starting at position 0, and pointer j for Bob starting at position n-1.

The key insight is that we can simulate the watering process directly. As they move toward the center simultaneously, we track:

• How much water each person currently has in their can
• When they need to refill (when current water < plant's requirement)

For each step:

1. Check if Alice has enough water for plants[i]. If not, refill and increment the refill counter
2. Water the plant and decrease Alice's water by plants[i]
3. Do the same for Bob with plants[j]
4. Move both pointers inward (i++, j--)

The simulation continues while i < j. When the pointers meet (i == j), there's one plant left that both could potentially water. According to the rules:

• The person with more water should water it
• We only need a refill if even the person with more water doesn't have enough

This is why the final check is max(a, b) < plants[i] when i == j. If true, one more refill is needed.

The beauty of this approach is its simplicity - we're literally following the problem's rules step by step, making it easy to implement and verify correctness. The time complexity is O(n) since we visit each plant exactly once, and space complexity is O(1) as we only use a few variables to track the state.

Learn more about Two Pointers patterns.

Solution Approach

We implement the two-pointer simulation approach to solve this problem:

Initialize Variables:

• a = capacityA and b = capacityB to track current water amounts for Alice and Bob
• ans = 0 to count total refills
• i = 0 and j = len(plants) - 1 as pointers for Alice and Bob's positions

Main Simulation Loop (while i < j):

For each iteration, we handle both Alice and Bob:

1. Alice's turn at position i:

   • Check if a < plants[i] (not enough water)
   • If true: refill (ans += 1 and a = capacityA)
   • Water the plant: a -= plants[i]

2. Bob's turn at position j:

   • Check if b < plants[j] (not enough water)
   • If true: refill (ans += 1 and b = capacityB)
   • Water the plant: b -= plants[j]

3. Move pointers inward:

   • i = i + 1 and j = j - 1

Handle the Middle Plant (when i == j):

After the loop, if there's a middle plant (odd number of plants), we need to determine who waters it:

• The person with more water should water it: max(a, b)
• If even the person with more water doesn't have enough (max(a, b) < plants[i]), add one more refill

This is handled elegantly in one line:

ans += i == j and max(a, b) < plants[i]

The expression evaluates to 1 (True) only when both conditions are met, adding exactly one refill when needed.

Time Complexity: O(n) - we visit each plant exactly once Space Complexity: O(1) - only using a constant amount of extra variables

Example Walkthrough

Let's trace through a small example to illustrate the solution approach.

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

Initial State:

• Alice: position i = 0, water a = 6
• Bob: position j = 4, water b = 5
• Refills: ans = 0

Step 1: (i = 0, j = 4)

• Alice waters plant 0 (needs 3): a = 6 - 3 = 3
• Bob waters plant 4 (needs 1): b = 5 - 1 = 4
• Move pointers: i = 1, j = 3

Step 2: (i = 1, j = 3)

• Alice waters plant 1 (needs 1): a = 3 - 1 = 2
• Bob waters plant 3 (needs 4): Has 4 water, exactly enough! b = 4 - 4 = 0
• Move pointers: i = 2, j = 2

Step 3: Loop ends since i == j

• Both Alice and Bob are at plant 2 (needs 2 water)
• Alice has 2 water, Bob has 0 water
• Since max(2, 0) = 2 and plant needs 2, Alice has exactly enough water
• No refill needed

Result: Total refills = 0

Another Example with Refills:

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

Step 1: (i = 0, j = 3)

• Alice waters plant 0 (needs 4): a = 4 - 4 = 0
• Bob checks plant 3 (needs 5): Has 3 water, not enough! Refill (ans = 1), then water: b = 3 - 5 = -2 → Actually b = capacityB - 5 = 3 - 5 is wrong. After refill: b = 3, then water: b = 3 - 5... Wait, capacity is only 3 but plant needs 5!

Let me fix this example:

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

Step 1: (i = 0, j = 3)

• Alice waters plant 0 (needs 2): a = 3 - 2 = 1
• Bob checks plant 3 (needs 2): Has 2 water, exactly enough! b = 2 - 2 = 0
• Move pointers: i = 1, j = 2

Step 2: (i = 1, j = 2)

• Alice waters plant 1 (needs 1): a = 1 - 1 = 0
• Bob checks plant 2 (needs 1): Has 0 water, not enough! Refill (ans = 1), then water: b = 2 - 1 = 1
• Move pointers: i = 2, j = 1

Step 3: Loop ends since i > j

Result: Total refills = 1

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the plants array.

The algorithm uses a two-pointer approach where pointer i starts from the beginning (index 0) and pointer j starts from the end (index len(plants) - 1). In each iteration of the while loop, both pointers move one step closer to each other (i increments and j decrements). The loop continues while i < j, meaning each element in the array is visited exactly once. After the loop, there's a constant-time check for the middle element when the array has odd length. Therefore, the total number of operations is proportional to the number of elements in the array, resulting in O(n) time complexity.

Space Complexity: O(1)

The algorithm only uses a fixed amount of extra space regardless of the input size. The variables used are:

• a and b for tracking current water amounts
• ans for counting refills
• i and j as pointers
• No additional data structures are created

Since the number of variables remains constant and doesn't scale with the input size, the space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Middle Plant Handling

Pitfall: A common mistake is forgetting to check if there's actually a middle plant when the number of plants is odd, or incorrectly determining who should water it.

Incorrect Implementation:

# Wrong: Always checking for middle plant even when n is even
if max(current_water_a, current_water_b) < plants[left]:
    refill_count += 1

# Wrong: Not considering who has more water
if current_water_a < plants[left]:
    refill_count += 1

Solution: Always verify that left == right after the loop to confirm there's a middle plant, and use the maximum of both water amounts to determine if a refill is needed:

if left == right and max(current_water_a, current_water_b) < plants[left]:
    refill_count += 1

2. Refilling After Watering Instead of Before

Pitfall: Checking for refill after attempting to water the plant, which would result in negative water amounts.

Incorrect Implementation:

# Wrong order - watering before checking capacity
current_water_a -= plants[left]
if current_water_a < 0:  # Now it's too late!
    refill_count += 1
    current_water_a = capacityA

Solution: Always check if refill is needed BEFORE watering:

if current_water_a < plants[left]:
    refill_count += 1
    current_water_a = capacityA
current_water_a -= plants[left]

3. Not Resetting to Full Capacity After Refill

Pitfall: Adding the capacity to current water instead of resetting to full capacity.

Incorrect Implementation:

if current_water_a < plants[left]:
    refill_count += 1
    current_water_a += capacityA  # Wrong! This adds to existing water

Solution: Reset to full capacity when refilling:

if current_water_a < plants[left]:
    refill_count += 1
    current_water_a = capacityA  # Correct: reset to full capacity

4. Off-by-One Errors with Pointers

Pitfall: Using wrong loop conditions or pointer updates that might skip plants or cause index out of bounds.

Incorrect Implementation:

# Wrong: using <= might process middle plant twice
while left <= right:
    # process both left and right
    left += 1
    right -= 1

Solution: Use left < right for the main loop and handle the middle plant separately:

while left < right:
    # process both left and right
    left += 1
    right -= 1

# Handle middle plant separately if it exists
if left == right:
    # handle middle plant