Skip to main content
Talentd

Watering Plants - Solution & Explanation

MediumArraySimulation21 min readAsked at: Amadeus, Google, Kla Tencor
Practice this problem

Problem Statement

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.length
  • 1 <= n <= 1000
  • 1 <= plants[i] <= 106
  • max(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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) - We go through each plant once.
Space Complexity: O(1) - Constant space use regardless of input size.

Try this approach in the editor →

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) - Single pass through the plants array.
Space Complexity: O(1) - Only uses fixed additional storage.

Try this approach in the editor →

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 update water = 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).

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach

Time Complexity: O(n) - We go through each plant once.
Space Complexity: O(1) - Constant space use regardless of input size.

Simulated Backtracking

Time Complexity: O(n) - Single pass through the plants array.
Space Complexity: O(1) - Only uses fixed additional storage.

Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Simulated BacktrackingO(n)O(1)Good for understanding the walking and refill process step-by-step
Greedy SimulationO(n)O(1)Preferred solution for interviews and production due to simple single-pass logic

Video Solution

Leetcode 2079 Watering Plants - Simplified Logic Explained With Examples & Java Code • AlgorithmicIQ • 1,689 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Watering Plants with our built-in code editor and test cases.

Practice on FleetCode
Previous

Watering Plants II