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:
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 the number of steps needed to water all the plants.
Example 1:
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:
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:
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.length1 <= n <= 10001 <= plants[i] <= 106max(plants[i]) <= capacity <= 109Problem Overview: You walk along a row of plants and water them from left to right using a watering can with fixed capacity. Each plant requires a certain amount of water. When the remaining water is not enough, you must walk back to the river to refill and then return to the current plant. The task is to compute the total number of steps taken.
Approach 1: Simulated Backtracking (O(n) time, O(1) space)
This approach directly simulates the walking process and treats every refill as a backtrack to the river. You iterate through the array and track the remaining water in the can. When the current plant requires more water than you have left, you simulate walking back to the river and returning by adding 2 * i steps, where i is the plant index. After refilling, you continue watering. The logic mirrors the real movement step-by-step, which makes the reasoning straightforward. Because each plant is processed once and the refill calculation is constant time, the overall complexity stays O(n) with O(1) extra space.
Approach 2: Greedy Simulation (O(n) time, O(1) space)
The greedy observation is that you should only refill when it becomes absolutely necessary. While iterating through the plants array, keep track of the remaining capacity in the watering can. If the remaining water is less than plants[i], the optimal move is to refill immediately before watering that plant. The cost of that refill is 2 * i steps because you walk from plant i back to the river and return. After refilling, subtract the plant’s water requirement and continue forward, adding one step for each move to the next plant. This greedy rule guarantees the minimum number of steps because any earlier refill would only add unnecessary travel. The algorithm performs a single pass over the array and uses constant extra memory.
Both implementations rely on simple iteration over an array and simulate the process of movement and refilling. The logic is essentially a simulation problem with a greedy decision about when to refill. The key insight is that every refill must occur exactly when the remaining capacity becomes insufficient, and the travel distance for that refill depends only on the current plant index.
Recommended for interviews: The greedy simulation approach is what interviewers typically expect. It demonstrates that you can model movement efficiently while minimizing unnecessary operations. Explaining the refill rule clearly shows understanding of greedy reasoning. The simulated backtracking explanation is still useful because it mirrors the real-world process and helps validate the step calculation.
In this approach, the task is to simulate the watering process while counting the number of steps. The key is to keep track of the remaining water capacity as you move forward, and calculate the steps needed to return and refill when required. This involves incrementing the steps based on whether we're moving forward to water the next plant or returning to the river.
This C code follows a simple and greedy logic where we always check if we have enough capacity to water the next plant. If we do, we move forward (adding one to the step count). If not, we simulate a return to the river and refill by doubling the steps to the current plant and re-watering it.
Time Complexity: O(n) - We go through each plant once.
Space Complexity: O(1) - Constant space use regardless of input size.
Another approach is to simulate the process with a backtracking mindset. For each plant, decide if it's optimal to water it with the remaining water or go back for a refill beforehand, keeping track of the decision impact on the overall steps count.
This C solution follows a backtracking-like approach where decisions on when to refill are made as we traverse. If we don't have enough water to proceed, we decide to refill accordingly and re-calculate steps while mimicking a backtracking return.
Time Complexity: O(n) - Single pass through the plants array.
Space Complexity: O(1) - Only uses fixed additional storage.
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(n) - We go through each plant once. |
| Simulated Backtracking | Time Complexity: O(n) - Single pass through the plants array. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulated Backtracking | O(n) | O(1) | Good for understanding the walking and refill process step-by-step |
| Greedy Simulation | O(n) | O(1) | Preferred solution for interviews and production due to simple single-pass logic |
Leetcode 2079 Watering Plants - Simplified Logic Explained With Examples & Java Code • AlgorithmicIQ • 1,641 views views
Watch 9 more video solutions →Practice Watering Plants with our built-in code editor and test cases.
Practice on FleetCode