Abstract / Summary

You must determine if all plants receive enough water based on given rules for how water spreads.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 49% (60k+ submissions).

Typical patterns to solve this problem:

• Array
• Simulation
• Two Pointers

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The minimumRefill method computes the smallest number of water refills required for two workers, Alice and Bob, to water a line of plants. Alice starts at the left end of the list, Bob at the right end, each carrying a water bottle with a fixed capacity. They move toward each other, watering plants sequentially. When a worker’s remaining water is insufficient for the next plant, a refill is counted and the bottle is restored to full capacity. The algorithm stops when the two pointers meet, handling the final plant specially if needed.

Initialization

refills = 0

left  = 0               # Alice's position
right = len(plants) - 1 # Bob's   position
alice = capacityA       # Alice's water
bob   = capacityB       # Bob's   water

The variables left and right serve as moving indices that converge toward the center of the array. alice and bob store the current amount of water each worker has, while refills accumulates the total number of times either worker refills their bottle.

Main Loop - Simultaneous Traversal

while left < right:
    # Alice
    if alice < plants[left]:
        refills += 1
        alice    = capacityA
    alice -= plants[left]
    left += 1

    # Bob
    if bob < plants[right]:
        refills += 1
        bob      = capacityB
    bob -= plants[right]
    right -= 1

The loop continues while the two pointers have not crossed. Inside each iteration, Alice processes the plant at index left. If her remaining water is less than the water needed for that plant, a refill is recorded and her water level is reset to the full capacity. After watering, her water is decreased by the plant’s requirement and the pointer advances. The same logic is applied to Bob for the plant at index right. By handling both workers in the same loop body, the algorithm ensures a single pass over the array, minimizing overhead.

Edge Cases Within the Loop

• When a plant requires exactly the amount of water currently held, the condition alice < plants[left] (or the analogous Bob condition) evaluates to false, so no refill occurs. The water is then reduced to zero, which is a valid state for the next iteration.
• If a plant’s water requirement exceeds the capacity of the worker’s bottle, the refill logic still works because the worker refills to full capacity before attempting to water. The subsequent subtraction will result in a negative value, but the algorithm’s design guarantees that such a scenario never arises because the problem constraints ensure each plant’s requirement does not exceed the respective capacity.

Final Plant Handling

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

When the pointers converge, there is exactly one plant left to water. The code compares the larger of the two remaining water amounts with the plant’s requirement. If neither worker has enough water, a single additional refill is counted. This logic correctly handles the case where one worker may have sufficient water while the other does not, avoiding unnecessary refills.

Edge Cases for the Meeting Point

• If the array length is odd, the central plant is processed only once by the final conditional block, preventing double counting.
• If both workers arrive at the same plant with zero water, the max function yields zero, triggering a refill as required.
• When the central plant’s requirement is zero, the condition fails and no extra refill is added, reflecting that no water is needed.

Performance Optimizations

The algorithm achieves optimal traversal by using two pointers that move inward from opposite ends, guaranteeing that each plant is examined exactly once. This eliminates the need for auxiliary data structures or multiple passes. The use of simple integer variables for water levels and counters ensures low overhead per iteration. By resetting the water amount only when necessary (i.e., when the current amount is insufficient), the code avoids redundant refill operations, which directly contributes to minimizing the final count.

The decision to handle Alice and Bob sequentially within the same loop iteration reduces branch misprediction costs compared to separate loops, as the processor can keep the loop’s control flow tight. Moreover, the final conditional block isolates the special case of a single remaining plant, preventing the main loop from performing extra checks for convergence, thereby keeping the hot path of the loop minimal.

Imagine two friends named Alice and Bob are standing at opposite ends of a row of thirsty plants that need watering. Alice starts at the very beginning of the row and Bob starts at the very end. Each person carries a watering can that holds a certain amount of water.

As they move towards each other, Alice checks the plant she is standing in front of. If her watering can has enough water to give that plant a drink, she pours it and moves to the next plant. But if her can is too empty, she walks back to the water tap to refill it, which counts as one refill, and then she waters the plant. Alice does this for every plant she reaches until she finishes her half of the row.

Bob does the exact same thing starting from the other side, checking his plant and refilling his can whenever he runs out of water. They keep working their way toward the middle of the line until they meet up.

Sometimes they might both arrive at the very last plant in the middle at the same time. When this happens, they look at who has more water left in their can. If neither person has enough water to cover that final thirsty plant, they have to refill one more time to finish the job. After everyone has watered their flowers, the total count of refills is added up.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Python	Java				TS
	WalkCCC	C++		Python	Java
	leetcode.ca	C++		Python	Java		Go	Rust	TS
	Progiez	C++		Python	Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis		JS
	fsq	C++
	JoshCrozier		JS
	lkwq007			Python
	suxrobGM					C#
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality