Watering Plants solution and explanation
Google
9 more videos on this problem
Leetcode 2079 Watering Plants - Simplified Logic Explained With Examples & Java CodeAlgorithmicIQ · 14:53 · 1K views
2079. Watering Plants (Leetcode Medium)Programming Live with Larry · 12:17 · 755 views
Leetcode Weekly Contest 268, (Medium)2079. Watering PlantsCompetitive Somya · 3:01 · 644 views
LC2079 Watering PlantsCSE Society · 11:30 · 507 views
Leetcode 2079. Watering PlantsElite Code · 14:57 · 262 views
watering-plants #LeetCode #java #coding #intervewQuestionsCodeVia · 3:57 · 165 views
Leetcode 2079 Watering PlantsMath Geeks · 3:19 · 114 views
Leetcode 2079. Watering Plants (simulation)LetsCode · 5:55 · 99 views
l 25 2079 Watering PlantsDD Does · 16:37 · 25 views
Leetcode 2079 JavaBenjamin Rudin · 7:48 · 11 views
The 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 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 <= 109
Approach overview
Problem 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.
Approach 1: Greedy Approach
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.
def wateringPlants(plants, capacity):
steps = 0
current_water = capacity
for i, plant in enumerate(plants):
if plant <= current_water:
steps += 1
else:
steps += 2 * i + 1
current_water = capacity
current_water -= plant
return steps
plants = [2, 2, 3, 3]
capacity = 5
print(f'Steps needed: {wateringPlants(plants, capacity)}')public class WateringPlants {
public static int wateringSteps(int[] plants, int capacity) {
int steps = 0, current_water = capacity;
for (int i = 0; i < plants.length; i++) {
if (plants[i] <= current_water) {
steps++;
} else {
steps += 2 * i + 1;
current_water = capacity;
}
current_water -= plants[i];
}
return steps;
}
public static void main(String[] args) {
int[] plants = {2, 2, 3, 3};
int capacity = 5;
System.out.println("Steps needed: " + wateringSteps(plants, capacity));
}
}#include <iostream>
#include <vector>
int wateringPlants(std::vector<int>& plants, int capacity) {
int steps = 0, current_water = capacity;
for (int i = 0; i < plants.size(); ++i) {
if (plants[i] <= current_water) {
steps++;
} else {
steps += 2 * i + 1;
current_water = capacity;
}
current_water -= plants[i];
}
return steps;
}
int main() {
std::vector<int> plants = {2, 2, 3, 3};
int capacity = 5;
int result = wateringPlants(plants, capacity);
std::cout << "Steps needed: " << result << std::endl;
return 0;
}function wateringPlants(plants, capacity) {
let steps = 0;
let current_water = capacity;
for (let i = 0; i < plants.length; i++) {
if (plants[i] <= current_water) {
steps++;
} else {
steps += 2 * i + 1;
current_water = capacity;
}
current_water -= plants[i];
}
return steps;
}
const plants = [2, 2, 3, 3];
const capacity = 5;
console.log(`Steps needed: ${wateringPlants(plants, capacity)}`);#include <stdio.h>
int wateringPlants(int* plants, int plantsSize, int capacity) {
int steps = 0, current_water = capacity;
for (int i = 0; i < plantsSize; ++i) {
if (plants[i] <= current_water) {
steps++; // Move to plant i
} else {
steps += 2 * i + 1; // Return to river and come back to plant i
current_water = capacity;
}
current_water -= plants[i];
}
return steps;
}
int main() {
int plants[] = {2, 2, 3, 3};
int capacity = 5;
int result = wateringPlants(plants, 4, capacity);
printf("Steps needed: %d\n", result);
return 0;
}using System;
public class WateringPlants {
public static int WateringSteps(int[] plants, int capacity) {
int steps = 0, current_water = capacity;
for (int i = 0; i < plants.Length; i++) {
if (plants[i] <= current_water) {
steps++;
} else {
steps += 2 * i + 1;
current_water = capacity;
}
current_water -= plants[i];
}
return steps;
}
public static void Main() {
int[] plants = {2, 2, 3, 3};
int capacity = 5;
Console.WriteLine("Steps needed: " + WateringSteps(plants, capacity));
}
}In this Python solution, we simulate the process of watering each plant by iterating through the list. The step count is adjusted based on whether there's enough water to water the next plant or if a refill is needed.
Time Complexity: O(n) - Single pass through the plants list.
Space Complexity: O(1) - Only a few extra variables used regardless of input size.
Approach 2: Simulated Backtracking
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.
def wateringPlants(plants, capacity):
steps = 0
current_water = capacity
for i, plant in enumerate(plants):
if plant > current_water:
steps += 2 * i
current_water = capacity
steps += 1
current_water -= plant
return steps
plants = [2, 2, 3, 3]
capacity = 5
print(f'Steps needed (Backtracking): {wateringPlants(plants, capacity)}')public class WateringPlants {
public static int wateringSteps(int[] plants, int capacity) {
int steps = 0, current_water = capacity;
for (int i = 0; i < plants.length; i++) {
if (plants[i] > current_water) {
steps += 2 * i;
current_water = capacity;
}
steps++;
current_water -= plants[i];
}
return steps;
}
public static void main(String[] args) {
int[] plants = {2, 2, 3, 3};
int capacity = 5;
System.out.println("Steps needed (Backtracking): " + wateringSteps(plants, capacity));
}
}#include <iostream>
#include <vector>
int wateringPlants(std::vector<int>& plants, int capacity) {
int steps = 0, current_water = capacity;
for (int i = 0; i < plants.size(); i++) {
if (plants[i] > current_water) {
steps += 2 * i; // Return and go back
current_water = capacity;
}
steps++;
current_water -= plants[i];
}
return steps;
}
int main() {
std::vector<int> plants = {2, 2, 3, 3};
int capacity = 5;
int result = wateringPlants(plants, capacity);
std::cout << "Steps needed (Backtracking): " << result << std::endl;
return 0;
}function wateringPlants(plants, capacity) {
let steps = 0;
let current_water = capacity;
for (let i = 0; i < plants.length; i++) {
if (plants[i] > current_water) {
steps += 2 * i;
current_water = capacity;
}
steps++;
current_water -= plants[i];
}
return steps;
}
const plants = [2, 2, 3, 3];
const capacity = 5;
console.log(`Steps needed (Backtracking): ${wateringPlants(plants, capacity)}`);#include <stdio.h>
int wateringPlants(int* plants, int plantsSize, int capacity) {
int steps = 0, current_water = capacity;
for (int i = 0; i < plantsSize; i++) {
if (plants[i] > current_water) {
steps += 2 * i; // Go back to river and come to plant i
current_water = capacity;
}
steps++; // Move to plant i
current_water -= plants[i];
}
return steps;
}
int main() {
int plants[] = {2, 2, 3, 3};
int capacity = 5;
int result = wateringPlants(plants, 4, capacity);
printf("Steps needed (Backtracking): %d\n", result);
return 0;
}using System;
public class WateringPlants {
public static int WateringSteps(int[] plants, int capacity) {
int steps = 0, current_water = capacity;
for (int i = 0; i < plants.Length; i++) {
if (plants[i] > current_water) {
steps += 2 * i;
current_water = capacity;
}
steps++;
current_water -= plants[i];
}
return steps;
}
public static void Main() {
int[] plants = {2, 2, 3, 3};
int capacity = 5;
Console.WriteLine("Steps needed (Backtracking): " + WateringSteps(plants, capacity));
}
}The Python code mimics a backtracking decision process, where if a plant requires more water than available, we calculate the steps as if returning was already decided based on current inadequacy.
Time Complexity: O(n) - Single iteration over the plants array.
Space Complexity: O(1) - Utilizes basic arithmetic in variable storage.
Approach 3: Simulation
We can simulate the process of watering the plants. We use a variable water to represent the current amount of water in the watering can, initially water = capacity.
We traverse the plants. For each plant:
- If the current amount of water in the watering can is enough to water this plant, we move forward one step, water this plant, and update
water = water - plants[i]. - Otherwise, we need to return to the river to refill the watering can, walk back to the current position, and then move forward one step. The number of steps we need is
i times 2 + 1. Then we water this plant and updatewater = capacity - plants[i].
Finally, return the total number of steps.
The time complexity is O(n), where n is the number of plants. The space complexity is O(1).
function wateringPlants(plants: number[], capacity: number): number {
let [ans, water] = [0, capacity];
for (let i = 0; i < plants.length; ++i) {
if (water >= plants[i]) {
water -= plants[i];
++ans;
} else {
water = capacity - plants[i];
ans += i * 2 + 1;
}
}
return ans;
}func wateringPlants(plants []int, capacity int) (ans int) {
water := capacity
for i, p := range plants {
if water >= p {
water -= p
ans++
} else {
water = capacity - p
ans += i*2 + 1
}
}
return
}impl Solution {
pub fn watering_plants(plants: Vec<i32>, capacity: i32) -> i32 {
let mut ans = 0;
let mut water = capacity;
for (i, &p) in plants.iter().enumerate() {
if water >= p {
water -= p;
ans += 1;
} else {
water = capacity - p;
ans += (i as i32) * 2 + 1;
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(n) - Single pass through the plants list. |
| Simulated Backtracking | Time Complexity: O(n) - Single iteration over the plants array. |
| Simulation | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Watering Plants easy or hard?
Watering Plants is rated Medium on LeetCode but behaves closer to an easy-to-medium simulation problem. The challenge lies in correctly modeling the refill movement and counting steps. Once the refill rule is identified, the implementation becomes a straightforward O(n) greedy simulation.
Watering Plants Python/Java solution
In Python or Java, the implementation uses a loop over the plants array while tracking remaining capacity and total steps. When capacity is insufficient, add 2 * i steps and reset the capacity to the initial value before watering the plant. The logic is identical across Python, Java, C++, JavaScript, and C#.
How to solve Watering Plants in O(n)?
Iterate through the plants array while maintaining the current water left in the can. If the remaining capacity is less than plants[i], add 2 * i steps to simulate walking back to the river and returning, then refill the can. Subtract plants[i] from the capacity and add one step for moving forward. This single-pass simulation achieves O(n) time.
What is the best approach for Watering Plants?
The greedy simulation approach is the most efficient and commonly expected solution. Iterate through the plants array while tracking the remaining water capacity. If the current plant requires more water than you have left, walk back to the river and return, which adds 2 * i steps. This runs in O(n) time and O(1) space.
Is Watering Plants asked at Google/Amazon/Meta?
Array simulation problems like Watering Plants commonly appear in technical interviews at companies such as Amazon and Google. They test your ability to model a real-world process and convert it into efficient step counting using simple iteration and greedy decisions.
What data structure is used in Watering Plants?
The problem primarily uses an array to represent the water requirement of each plant. The algorithm performs sequential traversal with a few integer variables to track steps and remaining capacity. No additional data structures such as stacks or hash maps are required.
What is the time complexity of Watering Plants?
The optimal solution runs in O(n) time because you traverse the plants array once. Each plant triggers constant-time operations such as checking remaining capacity and possibly adding refill steps. The algorithm uses O(1) additional space since it only stores counters for steps and remaining water.