LeetCode 2079 - Watering Plants

LeetCode Problem 2079

Difficulty: 🟡 Medium
Topics: Array, Simulation

Solution

Problem Understanding

This problem asks us to simulate watering a row of plants with a watering can that has a fixed capacity. The plants are arranged along a straight line with indices representing their positions. You start at a river located at position x = -1 where you can refill your watering can. Each plant requires a specific amount of water, given in the plants array.

The goal is to calculate the total number of steps required to water all plants while following the watering rules. You must water the plants in order from left to right. After watering a plant, if the remaining water in your can is insufficient for the next plant, you must return to the river to refill completely before continuing. Steps are measured as unit distance along the x-axis; moving one position left or right counts as one step. The constraints ensure the watering can is always large enough to water any single plant (capacity >= max(plants[i])), so we never face a scenario where a plant cannot be watered in one trip.

The input consists of an array of integers plants and a single integer capacity. The output is a single integer representing the total number of steps needed.

Important edge cases include having plants that exactly match the remaining water in the can, having a single plant, and situations where multiple returns to the river are required.

Approaches

The brute-force approach involves simulating each step along the x-axis, incrementing a counter for each move, and keeping track of the remaining water. While this will give the correct answer, it is inefficient for large arrays and high capacities because it simulates each individual step unnecessarily. For example, if the capacity is very large compared to the number of plants, moving back and forth from the river could be counted repeatedly in a naive per-step simulation.

The key insight for an optimal solution is to simulate watering at the plant level instead of the step level. We only need to track the remaining water in the can, the position of the next plant, and the cost of moving back to the river when a refill is needed. If the remaining water is sufficient for the next plant, we simply move one step forward. Otherwise, we calculate the round-trip distance to the river, add it to the step count, refill the can, and then water the plant.

This simulation is linear in the number of plants, since each plant is visited exactly once, and each refill only happens as needed.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(S) where S = total steps	O(1)	Simulate every single step along the x-axis
Optimal	O(n)	O(1)	Simulate watering at plant level, only counting steps between plants and refills

Algorithm Walkthrough

1. Initialize steps to 0 to keep track of the total distance walked.
2. Initialize water to capacity representing the current amount of water in the can.
3. Iterate over each plant at index i in plants.
4. Check if water is less than plants[i]. If yes, you need to refill:

• Add (i * 2) to steps to account for walking back to the river and then returning to the current plant. i is the distance from the river to the current plant.
• Reset water to capacity.

5. Water the current plant by subtracting plants[i] from water.
6. Increment steps by 1 to account for moving from the previous position to this plant.
7. After finishing the iteration, return steps as the total number of steps.

Why it works: The algorithm maintains the invariant that before watering a plant, we always have enough water. The steps counter accumulates exactly the distance moved between positions and refills. Since the plants are watered in order and refills only happen when necessary, the total number of steps is minimal and correct.

Python Solution

from typing import List

class Solution:
    def wateringPlants(self, plants: List[int], capacity: int) -> int:
        steps = 0
        water = capacity
        for i, need in enumerate(plants):
            if water < need:
                steps += i * 2
                water = capacity
            water -= need
            steps += 1
        return steps

The implementation follows the algorithm directly. We initialize the steps counter and water level. For each plant, we check if a refill is needed, update the step count for the round trip, refill, subtract the water needed for the plant, and increment steps for moving forward. The final steps value gives the total number of steps taken.

Go Solution

func wateringPlants(plants []int, capacity int) int {
    steps := 0
    water := capacity
    for i, need := range plants {
        if water < need {
            steps += i * 2
            water = capacity
        }
        water -= need
        steps += 1
    }
    return steps
}

The Go implementation mirrors the Python version closely. steps and water are initialized, and we iterate over the plants slice with range. The refill condition, water subtraction, and step increment logic are identical. Go handles integer arithmetic natively without special handling for overflow, since constraints ensure values remain manageable.

Worked Examples

Example 1: plants = [2,2,3,3], capacity = 5

i	need	water before	refill?	steps added	water after	total steps
0	2	5	No	1	3	1
1	2	3	No	1	1	2
2	3	1	Yes	4 (2*2)	5	6
2	3	5	No	1	2	7
3	3	2	Yes	6 (3*2)	5	13
3	3	5	No	1	2	14

Example 2: plants = [1,1,1,4,2,3], capacity = 4

i	need	water before	refill?	steps added	water after	total steps
0	1	4	No	1	3	1
1	1	3	No	1	2	2
2	1	2	No	1	1	3
3	4	1	Yes	6 (3*2)	4	9
3	4	4	No	1	0	10
4	2	0	Yes	8 (4*2)	4	18
4	2	4	No	1	2	19
5	3	2	Yes	10 (5*2)	4	29
5	3	4	No	1	1	30

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We iterate over each plant exactly once and perform constant-time operations per plant.
Space	O(1)	Only a few integer variables are used, regardless of input size.

The linear time complexity is optimal given that we must examine every plant at least once. No extra data structures are used, making the space complexity constant.

Test Cases

# Provided examples
assert Solution().wateringPlants([2,2,3,3], 5) == 14  # Example 1
assert Solution().wateringPlants([1,1,1,4,2,3], 4) == 30  # Example 2
assert Solution().wateringPlants([7,7,7,7,7,7,7], 8) == 49  # Example 3

# Edge cases
assert Solution().wateringPlants([1], 1) == 1  # Single plant
assert Solution().wateringPlants([1,1,1,1], 10) == 4  # Capacity larger than total
assert Solution().wateringPlants([5,5,5,5], 5) == 12  # Must refill after each plant
assert Solution().wateringPlants([3,2,2,3], 5) == 12  # Refill after middle plant

Test	Why
Single plant	Minimal input, should only take 1 step
Capacity larger than total	No refill needed, ensures algorithm handles oversized capacity
Must refill after each plant	Checks repeated refill logic correctness
Refill after middle plant	Verifies intermediate refill handling

Edge Cases

Single plant: A single plant requires minimal movement. The algorithm correctly handles i = 0 and counts only one step.

Plant equals capacity: When a plant requires exactly the remaining water in the can, no refill is triggered prematurely. The algorithm subtracts the water correctly and moves forward.

Multiple consecutive refills: For plants that require frequent refills, the algorithm correctly adds `2*i