Problem Description

You are given an array plants where plants[i] represents the amount of water the i-th plant needs. You also have a watering can with a fixed capacity capacity. You start at the beginning of the row of plants (index 0) with a full watering can, and move from left to right, watering each plant in order.

• For each plant, if you have enough water left in your can to water it, you water it and move to the next plant.
• If you do not have enough water, you must walk back to the river (at index -1) to refill your can, then return to the current plant and water it.
• Each step from one plant to the next (or to the river and back) counts as one step.
• Your goal is to determine the total number of steps required to water all the plants.

Constraints: Each plant must be watered in order. You can only refill at the river. The watering can's capacity is fixed and does not change.

Thought Process

At first glance, the problem seems to require simulating each step: walk to each plant, check if you have enough water, and refill if needed. A brute-force approach would be to simulate every single step, including all movements back and forth to the river, which could be inefficient.

However, we can optimize by recognizing that we only need to track:

• How much water remains in the can after each plant.
• When we need to refill (i.e., if the current plant needs more water than we have left).
• The total steps: 1 step per plant, plus the extra steps taken when refilling.

The key insight is to count steps efficiently by summing the walk to each plant, and only adding the extra steps for refills when necessary.

Solution Approach

We will solve the problem using a simple simulation with optimized step counting:

1. Initialize steps to 0 (to count total steps), and water to capacity (current water in the can).
2. Iterate through each plant, from left to right (index 0 to n-1):
• For each plant at index i, check if water is at least plants[i].
• If yes, water the plant (water -= plants[i]), and increment steps by 1 (move to next plant).
• If not, calculate the steps to walk back to the river and return: 2 * i (go back i steps, return i steps), refill the can, then water the plant.
• After refilling, decrement water by plants[i] and increment steps by 1 (for watering this plant).
3. Continue until all plants are watered.
4. Return the total steps.

This approach ensures that we only add extra steps when a refill is needed, and otherwise simply move from plant to plant.

Example Walkthrough

Let's consider plants = [2, 4, 5, 1, 2] and capacity = 6.

• Start at plant 0 with 6 water. Needs 2. Water it (remaining: 4). Steps: 1.
• Plant 1 needs 4. Have 4. Water it (remaining: 0). Steps: 2.
• Plant 2 needs 5. Have 0. Not enough! Walk back to river (2 steps), refill, walk to plant 2 (2 steps), water it (remaining: 1). Steps: 2 (previous) + 4 (refill) + 1 (water) = 7.
• Plant 3 needs 1. Have 1. Water it (remaining: 0). Steps: 8.
• Plant 4 needs 2. Have 0. Not enough! Walk back to river (4 steps), refill, walk to plant 4 (4 steps), water it (remaining: 4). Steps: 8 (previous) + 8 (refill) + 1 (water) = 17.

Final answer: 17 steps.

Time and Space Complexity

• Brute-force approach: If we simulated every single step (including every back-and-forth movement), the time complexity would still be O(n), but with much more overhead per step.
• Optimized approach: We process each plant once, so time complexity is O(n), where n is the number of plants.
• Space complexity: We only use a few variables for counting; no extra data structures. Space complexity is O(1).

Summary

The Watering Plants problem can be solved efficiently by simulating the process and only counting extra steps when a refill is necessary. By iterating over the plants and tracking the remaining water, we avoid unnecessary computation and keep the solution clean and efficient. The algorithm is straightforward, easy to implement, and runs in linear time with constant space.

Code Implementation

class Solution:
    def wateringPlants(self, plants, capacity):
        steps = 0
        water = capacity
        for i, need in enumerate(plants):
            if water >= need:
                steps += 1
                water -= need
            else:
                # Go back to river and return
                steps += 2 * i + 1
                water = capacity - need
        return steps
      

class Solution {
public:
    int wateringPlants(vector<int>& plants, int capacity) {
        int steps = 0;
        int water = capacity;
        for (int i = 0; i < plants.size(); ++i) {
            if (water >= plants[i]) {
                steps += 1;
                water -= plants[i];
            } else {
                steps += 2 * i + 1;
                water = capacity - plants[i];
            }
        }
        return steps;
    }
};
      

class Solution {
    public int wateringPlants(int[] plants, int capacity) {
        int steps = 0;
        int water = capacity;
        for (int i = 0; i < plants.length; i++) {
            if (water >= plants[i]) {
                steps += 1;
                water -= plants[i];
            } else {
                steps += 2 * i + 1;
                water = capacity - plants[i];
            }
        }
        return steps;
    }
}
      

var wateringPlants = function(plants, capacity) {
    let steps = 0;
    let water = capacity;
    for (let i = 0; i < plants.length; i++) {
        if (water >= plants[i]) {
            steps += 1;
            water -= plants[i];
        } else {
            steps += 2 * i + 1;
            water = capacity - plants[i];
        }
    }
    return steps;
};