LeetCode 2105 - Watering Plants II

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Simulation

Solution

Problem Understanding

In this problem, we are given a row of plants where each plant requires a certain amount of water. Two people, Alice and Bob, water the plants simultaneously from opposite ends of the array.

Alice starts from the left side at index 0 and moves toward the right. Bob starts from the right side at index n - 1 and moves toward the left. Each person has their own watering can with a fixed maximum capacity. Initially, both cans are completely full.

For every plant they encounter, they must fully water it in one action. If the remaining water in their can is insufficient, they are required to refill before watering that plant. Refilling happens instantly, but each refill must be counted.

The goal is to compute the total number of refills required for both Alice and Bob to water all plants.

The interesting part of the problem occurs when both pointers meet at the same plant. In that situation:

Whoever currently has more water remaining waters the plant.
If both have the same amount, Alice waters it.

The input consists of:

plants, an array where plants[i] is the amount of water needed for plant i
capacityA, Alice's watering can capacity
capacityB, Bob's watering can capacity

The output is a single integer representing the minimum number of refills needed.

The constraints are important:

n can be as large as 10^5
Water capacities and plant requirements can be very large
Every plant's water requirement is guaranteed to fit within both watering cans

These constraints immediately rule out unnecessarily expensive simulations or repeated recomputation. We need a linear time solution.

Several edge cases are important:

A single plant, where only one of Alice or Bob waters it
Cases where both reach the middle plant simultaneously
Situations where one or both must refill immediately before watering
Cases where no refill is needed at all
Cases where every step requires a refill

Because the plants are processed exactly once from both ends, the problem strongly suggests a two pointer simulation approach.

Approaches

Brute Force Approach

A brute force simulation could explicitly model the passage of time and repeatedly determine which person waters which plant at every moment.

We could maintain separate states for Alice and Bob, simulate each watering operation individually, and repeatedly compare positions and remaining capacities. While this works conceptually, it introduces unnecessary complexity. The plants are always watered in deterministic order, and there is no branching or backtracking.

Another inefficient variation would repeatedly recompute remaining capacities or maintain extra structures tracking watering events. These approaches still eventually process each plant, but with unnecessary overhead.

The brute force approach is correct because it follows the exact rules of the problem statement. However, it is more complicated than necessary and may introduce extra processing beyond linear time.

Optimal Approach

The key observation is that the watering order is completely predetermined:

Alice always moves left to right
Bob always moves right to left
Each plant is watered exactly once

This means we can process the array using two pointers:

left for Alice
right for Bob

We also maintain:

Alice's remaining water
Bob's remaining water
Total refill count

At every step:

Alice handles plants[left]
Bob handles plants[right]

If either person lacks enough water, they refill first.

The only special case occurs when left == right, meaning both arrive at the same plant. At that point, we simply choose the person with more remaining water. If neither has enough, one refill is required.

This leads to a clean O(n) simulation with constant extra space.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n) to O(n²) depending on implementation	O(1) to O(n)	Simulates watering with unnecessary overhead
Optimal	O(n)	O(1)	Two pointer simulation processes each plant once

Algorithm Walkthrough

Initialize two pointers:

left = 0
right = n - 1

Alice will process plants from the left side, while Bob processes plants from the right side. 2. Initialize the remaining water amounts:

waterA = capacityA
waterB = capacityB

Both watering cans begin completely full. 3. Initialize a counter refills = 0.

This variable tracks the total number of refills performed. 4. Continue processing while left < right.

This means Alice and Bob are still watering different plants. 5. For Alice:

If waterA < plants[left], she cannot fully water the current plant.
Increment refills
Reset waterA = capacityA
Subtract the plant requirement from waterA

For Bob:

If waterB < plants[right], he must refill first.
Increment refills
Reset waterB = capacityB
Subtract the plant requirement from waterB

Move both pointers inward:

left += 1
right -= 1

After the loop, check whether left == right.

This means one middle plant remains unwatered. 9. Determine who waters the middle plant:

If waterA >= waterB, Alice attempts it
Otherwise Bob attempts it

If the chosen person's remaining water is insufficient:

Increment refills

Return refills.

Why it works

The algorithm works because the watering order is fixed and deterministic. Every plant is assigned to exactly one person based on pointer positions. At every step, the algorithm maintains the invariant that all plants outside the current [left, right] range have already been correctly watered with the minimum required refills.

The middle plant logic correctly follows the tie breaking rule from the problem statement. Since every plant is processed exactly once, and every refill is counted exactly when necessary, the final refill count is correct.

Python Solution

from typing import List

class Solution:
    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:
        left = 0
        right = len(plants) - 1

        waterA = capacityA
        waterB = capacityB

        refills = 0

        while left < right:
            if waterA < plants[left]:
                refills += 1
                waterA = capacityA

            waterA -= plants[left]

            if waterB < plants[right]:
                refills += 1
                waterB = capacityB

            waterB -= plants[right]

            left += 1
            right -= 1

        if left == right:
            remaining = max(waterA, waterB)

            if remaining < plants[left]:
                refills += 1

        return refills

The implementation directly follows the two pointer simulation described earlier.

The variables left and right track which plants Alice and Bob are currently responsible for. The variables waterA and waterB store the remaining water in each watering can.

Inside the main loop, we first check whether Alice has enough water for the current left plant. If not, we count a refill and restore her can to full capacity. After watering the plant, we subtract the required amount.

Bob follows the exact same logic from the opposite side.

After both plants are processed, the pointers move inward.

The final if left == right block handles the middle plant when the array length is odd. According to the problem rules, the person with more remaining water handles the plant. If that person still lacks enough water, exactly one refill is required.

The algorithm processes each plant exactly once, which guarantees linear time complexity.

Go Solution

func minimumRefill(plants []int, capacityA int, capacityB int) int {
	left := 0
	right := len(plants) - 1

	waterA := capacityA
	waterB := capacityB

	refills := 0

	for left < right {
		if waterA < plants[left] {
			refills++
			waterA = capacityA
		}

		waterA -= plants[left]

		if waterB < plants[right] {
			refills++
			waterB = capacityB
		}

		waterB -= plants[right]

		left++
		right--
	}

	if left == right {
		remaining := waterA
		if waterB > remaining {
			remaining = waterB
		}

		if remaining < plants[left] {
			refills++
		}
	}

	return refills
}

The Go implementation mirrors the Python solution closely.

Go does not provide a built in max function for integers, so we manually compute the larger remaining water amount for the middle plant case.

The solution uses only primitive integer variables and slice indexing, so memory usage remains constant. Integer overflow is not a concern because Go's int type comfortably handles the given constraints.

Worked Examples

Example 1

Input:

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

Initial state:

Step	left	right	waterA	waterB	refills
Start	0	3	5	5	0

First iteration

Alice waters plant 0 requiring 2.

waterA = 5 - 2 = 3

Bob waters plant 3 requiring 3.

waterB = 5 - 3 = 2

Step	left	right	waterA	waterB	refills
After iteration 1	1	2	3	2	0

Second iteration

Alice waters plant 1 requiring 2.

waterA = 3 - 2 = 1

Bob needs 3 units for plant 2, but only has 2.

Refill Bob
refills = 1
waterB = 5 - 3 = 2

Step	left	right	waterA	waterB	refills
Final	2	1	1	2	1

Result:

Example 2

Input:

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

Initial state:

Step	left	right	waterA	waterB	refills
Start	0	3	3	4	0

First iteration

Alice waters plant 0.

waterA = 1

Bob waters plant 3.

waterB = 1

Step	left	right	waterA	waterB	refills
After iteration 1	1	2	1	1	0

Second iteration

Alice needs 2, but only has 1.

Refill
refills = 1
waterA = 3 - 2 = 1

Bob needs 3, but only has 1.

Refill
refills = 2
waterB = 4 - 3 = 1

Step	left	right	waterA	waterB	refills
Final	2	1	1	1	2

Result:

Example 3

Input:

plants = [5]
capacityA = 10
capacityB = 8

Since there is only one plant:

Alice has more water than Bob
Alice waters the plant directly
No refill needed

Step	left	right	waterA	waterB	refills
Final	0	0	10	8	0

Result:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each plant is processed exactly once
Space	O(1)	Only a few integer variables are used

The algorithm uses two pointers that move inward from opposite ends of the array. Every iteration processes one or two plants, and no plant is revisited. Therefore, the total runtime grows linearly with the number of plants.

The solution stores only constant extra state variables such as pointer positions, remaining water amounts, and the refill counter. No auxiliary arrays or data structures are required.

Test Cases

from typing import List

class Solution:
    def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:
        left = 0
        right = len(plants) - 1

        waterA = capacityA
        waterB = capacityB

        refills = 0

        while left < right:
            if waterA < plants[left]:
                refills += 1
                waterA = capacityA

            waterA -= plants[left]

            if waterB < plants[right]:
                refills += 1
                waterB = capacityB

            waterB -= plants[right]

            left += 1
            right -= 1

        if left == right:
            if max(waterA, waterB) < plants[left]:
                refills += 1

        return refills

sol = Solution()

assert sol.minimumRefill([2,2,3,3], 5, 5) == 1  # provided example 1
assert sol.minimumRefill([2,2,3,3], 3, 4) == 2  # provided example 2
assert sol.minimumRefill([5], 10, 8) == 0  # single plant, no refill
assert sol.minimumRefill([5], 3, 10) == 0  # Bob handles middle plant
assert sol.minimumRefill([1,1,1,1], 2, 2) == 0  # no refill needed
assert sol.minimumRefill([3,3,3,3], 3, 3) == 2  # refill every second plant
assert sol.minimumRefill([1,2,4,4,5], 6, 5) == 2  # odd length with middle plant
assert sol.minimumRefill([2], 2, 2) == 0  # exact capacity match
assert sol.minimumRefill([7,7,7], 8, 8) == 1  # middle plant requires refill
assert sol.minimumRefill([1,2,3,4,5,6], 10, 10) == 2  # larger mixed case

Test	Why
`[2,2,3,3], 5, 5`	Validates standard two pointer behavior
`[2,2,3,3], 3, 4`	Tests simultaneous refill requirement
`[5], 10, 8`	Single plant handled by Alice
`[5], 3, 10`	Single plant handled by Bob
`[1,1,1,1], 2, 2`	Confirms no unnecessary refills
`[3,3,3,3], 3, 3`	Tests repeated refill behavior
`[1,2,4,4,5], 6, 5`	Validates odd length middle handling
`[2], 2, 2`	Exact capacity edge case
`[7,7,7], 8, 8`	Middle plant requires additional refill
`[1,2,3,4,5,6], 10, 10`	General mixed scenario

Edge Cases

Single Plant

When the array contains only one plant, both Alice and Bob reach it simultaneously. A common mistake is attempting to let both process the same plant independently, which would double count watering or refills.

The implementation correctly handles this by exiting the main loop immediately and processing the middle plant separately. It compares remaining water amounts and chooses the correct person according to the problem rules.

Exact Capacity Match

A subtle bug can occur when a watering can contains exactly the amount needed for a plant. Some incorrect implementations use <= instead of < when checking refill conditions, causing unnecessary refills.

This solution correctly checks:

if waterA < plants[left]:

which means a refill only occurs when the remaining water is strictly insufficient.

Odd Number of Plants

When n is odd, Alice and Bob eventually meet at the same middle plant. Incorrect solutions sometimes allow both to water it or forget to apply the tie breaking rule.

This implementation explicitly handles the middle plant after the main loop. It selects the person with more remaining water, and if both have equal water, Alice is chosen automatically because max(waterA, waterB) matches the problem requirement.