We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Watering Plants

Number: 1310

Difficulty: Medium

Paid? No

Companies: Google, Amadeus

Problem Description

You are given a row of n plants positioned from x = 0 to x = n-1 and a river located at x = -1. Each plant requires a specific amount of water, and you start at the river with a fully-filled watering can. You water the plants in order from left to right. After watering each plant, if you do not have enough water to completely water the next plant, you must walk back to the river to refill your can. The goal is to determine the total number of steps required to water all the plants, where moving one unit along the x-axis represents one step.

Key Insights

  • The plants are arranged in a row corresponding to their indices.
  • You start at the river (x = -1) with a full watering can.
  • When the remaining water in the can is not enough for the next plant, you must walk back to the river (a round trip).
  • Each refill requires adding twice the current plant index (i steps back and i steps forward).
  • The steps required to reach each plant are determined by moving sequentially along the x-axis.

Space and Time Complexity

Time Complexity: O(n) where n is the number of plants (one pass over the array). Space Complexity: O(1) additional space.

Solution

We simulate the watering process by iterating over each plant. Start with a full watering can and decrement the water by the amount required for the current plant. If there isn’t enough water to handle the next plant, simulate a refill by adding the distance from the current plant back to the river and then returning to that plant's position (i.e., add 2 * i steps), and then refill the watering can. Always count the step taken to move to the next plant. This simulation accurately tracks the total number of steps required.

Code Solutions

# Python solution for the problem

def wateringPlants(plants, capacity):
    steps = 0             # Total steps counter
    remaining = capacity  # Water remaining in the watering can
    
    # Iterate over every plant using its index
    for i, waterNeeded in enumerate(plants):
        # If there's not enough water for the current plant,
        # simulate a refill by walking back to the river and then returning
        if remaining < waterNeeded:
            steps += 2 * i  # Round trip distance from plant i back to river and back to plant i
            remaining = capacity  # Refill the watering can
            
        remaining -= waterNeeded  # Water the current plant
        steps += 1                # Move to the next plant (or finish if last plant)
        
    return steps

# Example usage:
print(wateringPlants([2,2,3,3], 5))  # Expected output: 14
← Back to All Questions