Problem Description

You have n plants arranged in a row in your garden, labeled from 0 to n - 1. Each plant is positioned at coordinate x = i (where i is the plant's index). There's a river located at x = -1 where you can refill your watering can.

You're given:

• An array plants where plants[i] represents the amount of water needed by the i-th plant
• An integer capacity representing the maximum water your watering can hold

Starting from the river (position x = -1), you need to water all plants following these rules:

1. Water plants in order: You must water plants from left to right (index 0 to n-1)
2. Refill when necessary: If you don't have enough water to completely water the next plant, you must return to the river to refill your watering can to full capacity
3. No early refilling: You cannot refill the watering can unless you don't have enough water for the next plant

Movement costs:

• Each step along the x-axis (moving one unit) counts as one step
• To move from position a to position b, you need |b - a| steps

The task is to find the minimum number of steps needed to water all plants.

Example walkthrough: If plants = [2, 2, 3, 3] and capacity = 5:

• Start at river (-1), move to plant 0 (1 step), water it (water left: 3)
• Move to plant 1 (1 step), water it (water left: 1)
• Not enough for plant 2, return to river (2 steps), then back to plant 2 (3 steps), water it (water left: 2)
• Move to plant 3 (1 step), not enough water, return to river (4 steps), then back to plant 3 (4 steps), water it
• Total steps: 1 + 1 + 2 + 3 + 1 + 4 + 4 = 16 steps

Intuition

The key insight is that we're forced to water plants in order from left to right, and we can only refill when we don't have enough water for the next plant. This makes the problem a straightforward simulation.

Let's think about the movement pattern:

• When we have enough water, we simply move forward one step to the next plant
• When we don't have enough water, we must go back to the river and return to our current position

For any plant at position i, if we need to refill:

• We're currently at position i-1 (just finished watering the previous plant)
• We need to go back to the river at position -1: this takes i steps
• Then we need to return from the river to plant i: this takes i + 1 steps
• Total steps for refilling and reaching plant i: i + (i + 1) = 2i + 1 steps

This observation leads to our solution strategy:

1. Keep track of current water in the can
2. For each plant, check if we have enough water
3. If yes, move forward 1 step and water the plant
4. If no, calculate the refill journey as 2 * current_position + 1 steps, refill, and water the plant

The beauty of this approach is that we don't need to explicitly track our position. Since we're moving sequentially through plants, the index i tells us exactly where we are. When we're about to water plant i, we're standing at position i-1, making the refill calculation straightforward.

Solution Approach

We implement a simulation approach that tracks our water level as we traverse the plants from left to right.

Variables needed:

• ans: Tracks the total number of steps taken
• water: Current amount of water in the watering can (initially set to capacity)

Algorithm:

We iterate through each plant using its index i and water requirement p:

1. Check if we have enough water (water >= p):
   • If yes: We can water this plant directly
     • Move forward 1 step: ans += 1
     • Use the water: water -= p
2. If we don't have enough water (water < p):
   • We must return to the river and come back
     • Calculate round trip: Since we're at position i-1 (having just watered the previous plant), we need:
       • i steps to return to river (from position i-1 to -1)
       • i + 1 steps to come back to plant i (from -1 to i)
       • Total: i * 2 + 1 steps
     • Update steps: ans += i * 2 + 1
     • Refill and use water for current plant: water = capacity - p

Why this works:

• The greedy approach is optimal because we're forced to water plants in order
• We only refill when absolutely necessary (can't water the next plant)
• The formula i * 2 + 1 efficiently calculates the round trip without explicitly tracking position

Time Complexity: O(n) where n is the number of plants - we visit each plant exactly once

Space Complexity: O(1) - we only use a constant amount of extra space for variables

Example Walkthrough

Let's walk through a small example with plants = [3, 1, 2] and capacity = 4.

Initial State:

• Starting at river (position -1)
• Watering can is full with 4 units of water
• Total steps = 0

Plant 0 (needs 3 units):

• Check: Do we have enough water? Yes! (4 ≥ 3)
• Action: Move from river to plant 0 (1 step)
• Water the plant: 4 - 3 = 1 unit remaining
• Total steps = 1

Plant 1 (needs 1 unit):

• Check: Do we have enough water? Yes! (1 ≥ 1)
• Action: Move from plant 0 to plant 1 (1 step)
• Water the plant: 1 - 1 = 0 units remaining
• Total steps = 1 + 1 = 2

Plant 2 (needs 2 units):

• Check: Do we have enough water? No! (0 < 2)
• Action: Must refill
  • We're at position 1 (just watered plant 1)
  • Return to river: 2 steps (from position 1 to -1)
  • Come back to plant 2: 3 steps (from -1 to position 2)
  • Total for this refill trip: 2 × 2 + 1 = 5 steps
• Refill can to full capacity (4 units) and water plant 2
• Water remaining: 4 - 2 = 2 units
• Total steps = 2 + 5 = 7

Final Answer: 7 steps

This example demonstrates both scenarios:

1. When we have enough water (plants 0 and 1): we simply move forward 1 step
2. When we need to refill (plant 2): we use the formula 2i + 1 where i is the current plant index

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the number of plants. The algorithm iterates through the list of plants exactly once using a single for loop with enumerate(plants). Each iteration performs a constant amount of work - checking conditions, updating variables, and performing basic arithmetic operations. Therefore, the total time complexity is linear with respect to the number of plants.

The space complexity is O(1). The algorithm only uses a fixed amount of extra space regardless of the input size. The variables ans (tracking total steps), water (tracking current water amount), i (loop index), and p (current plant's water requirement) are the only additional storage used, and their space requirement does not grow with the size of the input array.

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

Common Pitfalls

Pitfall 1: Incorrectly Calculating Position After Watering Previous Plants

The Mistake: A common error is assuming you're at position i when checking if you need to refill for plant i, rather than position i-1. This leads to an incorrect distance calculation for the return trip.

Incorrect Implementation:

# WRONG: Assumes we're already at position i
if current_water < water_needed:
    total_steps += (i + 1) * 2  # Incorrect formula

Why it's wrong: After watering plant i-1, you're standing at position i-1, not at position i. The distance to the river from position i-1 is i steps (since the river is at position -1).

Correct Implementation:

# CORRECT: We're at position i-1 after watering the previous plant
if current_water < water_needed:
    total_steps += i * 2 + 1  # Correct: i steps back, i+1 steps forward

Pitfall 2: Forgetting to Account for the Initial Movement from River

The Mistake: Some implementations forget that we start at the river (position -1) and need to count the initial step(s) to reach the first plant.

Incorrect Implementation:

# WRONG: Doesn't properly handle the first plant
total_steps = 0
for i, water_needed in enumerate(plants):
    if i == 0:
        # Forgot to add the initial step from river to plant 0
        current_water -= water_needed
    # ... rest of logic

Correct Implementation: Both approaches handle this correctly by either:

• Adding 1 step for each plant movement (including the first one)
• Or explicitly calculating the distance from the river when refilling

Pitfall 3: Off-by-One Error in Round Trip Calculation

The Mistake: Miscounting the steps needed for a round trip, especially forgetting that moving from position -1 to position i requires i + 1 steps, not i steps.

Visual Example:

River   Plant0  Plant1  Plant2
 -1       0       1       2
  |-------|-------|-------|
     1       2       3     (steps from river)

Incorrect Calculation:

# WRONG: Forgets the river is at -1, not 0
steps_to_plant_from_river = i  # Should be i + 1

Correct Calculation:

# CORRECT: Accounts for river being at position -1
steps_back_to_river = i  # From position i-1 to -1
steps_to_current_plant = i + 1  # From -1 to i
total_round_trip = i * 2 + 1