Problem

You want to water n plants in your garden with a watering can. The plants are arranged in a row and are labeled from 0 to n - 1 from left to right where the ith plant is located at x = i. There is a river at x = -1 that you can refill your watering can at.

Each plant needs a specific amount of water. You will water the plants in the following way:

  • Water the plants in order from left to right.
  • After watering the current plant, if you do not have enough water to completely water the next plant, return to the river to fully refill the watering can.
  • You cannot refill the watering can early.

You are initially at the river (i.e., x = -1). It takes one step to move one unit on the x-axis.

Given a 0-indexed integer array plants of n integers, where plants[i] is the amount of water the ith plant needs, and an integer capacity representing the watering can capacity, return thenumber of steps needed to water all the plants.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Input: plants = [2,2,3,3], capacity = 5
Output: 14
Explanation: Start at the river with a full watering can:
- Walk to plant 0 (1 step) and water it. Watering can has 3 units of water.
- Walk to plant 1 (1 step) and water it. Watering can has 1 unit of water.
- Since you cannot completely water plant 2, walk back to the river to refill (2 steps).
- Walk to plant 2 (3 steps) and water it. Watering can has 2 units of water.
- Since you cannot completely water plant 3, walk back to the river to refill (3 steps).
- Walk to plant 3 (4 steps) and water it.
Steps needed = 1 + 1 + 2 + 3 + 3 + 4 = 14.

Example 2

1
2
3
4
5
6
7
8

Input: plants = [1,1,1,4,2,3], capacity = 4
Output: 30
Explanation: Start at the river with a full watering can:
- Water plants 0, 1, and 2 (3 steps). Return to river (3 steps).
- Water plant 3 (4 steps). Return to river (4 steps).
- Water plant 4 (5 steps). Return to river (5 steps).
- Water plant 5 (6 steps).
Steps needed = 3 + 3 + 4 + 4 + 5 + 5 + 6 = 30.

Example 3

1
2
3
4

Input: plants = [7,7,7,7,7,7,7], capacity = 8
Output: 49
Explanation: You have to refill before watering each plant.
Steps needed = 1 + 1 + 2 + 2 + 3 + 3 + 4 + 4 + 5 + 5 + 6 + 6 + 7 = 49.

Constraints

  • n == plants.length
  • 1 <= n <= 1000
  • 1 <= plants[i] <= 10^6
  • max(plants[i]) <= capacity <= 10^9

Solution

Method 1 – Simulation with Greedy Refills

Intuition

We simulate the process step by step, always walking to the next plant, watering it, and refilling only when necessary. The number of steps is the sum of all moves, including returns to the river.

Approach

  1. Start at the river (position -1) with a full can.
  2. For each plant:
    • If enough water, walk to the plant, water it, and update remaining water.
    • If not enough, walk back to the river, refill, and walk to the plant again.
  3. Accumulate the total steps for all moves.
  4. Return the total steps.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    int wateringPlants(vector<int>& plants, int capacity) {
        int ans = 0, curr = capacity;
        for (int i = 0; i < plants.size(); ++i) {
            if (curr < plants[i]) {
                ans += 2 * i;
                curr = capacity;
            }
            ans++;
            curr -= plants[i];
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func wateringPlants(plants []int, capacity int) int {
    ans, curr := 0, capacity
    for i, v := range plants {
        if curr < v {
            ans += 2 * i
            curr = capacity
        }
        ans++
        curr -= v
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int wateringPlants(int[] plants, int capacity) {
        int ans = 0, curr = capacity;
        for (int i = 0; i < plants.length; i++) {
            if (curr < plants[i]) {
                ans += 2 * i;
                curr = capacity;
            }
            ans++;
            curr -= plants[i];
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun wateringPlants(plants: IntArray, capacity: Int): Int {
        var ans = 0
        var curr = capacity
        for (i in plants.indices) {
            if (curr < plants[i]) {
                ans += 2 * i
                curr = capacity
            }
            ans++
            curr -= plants[i]
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

from typing import List
class Solution:
    def wateringPlants(self, plants: List[int], capacity: int) -> int:
        ans = 0
        curr = capacity
        for i, v in enumerate(plants):
            if curr < v:
                ans += 2 * i
                curr = capacity
            ans += 1
            curr -= v
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

impl Solution {
    pub fn watering_plants(plants: Vec<i32>, capacity: i32) -> i32 {
        let mut ans = 0;
        let mut curr = capacity;
        for (i, &v) in plants.iter().enumerate() {
            if curr < v {
                ans += 2 * i as i32;
                curr = capacity;
            }
            ans += 1;
            curr -= v;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    wateringPlants(plants: number[], capacity: number): number {
        let ans = 0, curr = capacity;
        for (let i = 0; i < plants.length; i++) {
            if (curr < plants[i]) {
                ans += 2 * i;
                curr = capacity;
            }
            ans++;
            curr -= plants[i];
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — We process each plant once.
  • 🧺 Space complexity: O(1) — Only a constant amount of extra space is used.