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 II

Number: 2228

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Alice and Bob water n plants arranged in a row. Alice starts from the left and Bob from the right, watering one plant at a time concurrently. Each plant requires a certain amount of water and they refill their watering can when there isn’t enough water to completely water the plant. In case they meet at the same plant, the one with more water (or Alice if equal) waters it. The task is to compute how many times they need to refill their watering cans to water all plants.

Key Insights

  • Two simultaneous pointers: one starting from the beginning (Alice) and one from the end (Bob).
  • Each person checks if their remaining water is enough; if not, they refill before watering the plant.
  • When both reach the same plant, compare remaining water to decide who will water it.
  • Simulation of the watering process guarantees an O(n) time complexity as each plant is visited exactly once.

Space and Time Complexity

Time Complexity: O(n) since we traverse the plants array using two pointers. Space Complexity: O(1) as only a few extra variables are used.

Solution

We use a two-pointer approach, with one pointer for Alice (starting at index 0) and one for Bob (starting at index n-1). For each plant:

  • Check if the current water is sufficient to water the plant.
  • If not, refill (increase the counter) and deduct the water needed.
  • When both pointers meet, determine who will water the plant by comparing the remaining water amounts; in case of a tie, Alice waters it. This simulation directly follows the problem rules and guarantees that we count each refill correctly.

Code Solutions

# Python solution for Watering Plants II

def minimumRefill(plants, capacityA, capacityB):
    # Initialize left and right pointers along with current water levels and refill count
    left, right = 0, len(plants) - 1
    waterA, waterB = capacityA, capacityB
    refills = 0

    # Process plants while pointers do not cross
    while left < right:
        # For Alice: Check if water is enough to water the current plant
        if waterA < plants[left]:
            refills += 1           # Refill happens
            waterA = capacityA     # Reset water to full capacity
        waterA -= plants[left]     # Water the plant
        left += 1                # Move to next plant for Alice

        # For Bob: Check if water is enough to water the current plant
        if waterB < plants[right]:
            refills += 1           # Refill happens
            waterB = capacityB     # Reset water to full capacity
        waterB -= plants[right]    # Water the plant
        right -= 1               # Move to next plant for Bob

    # When both pointers meet at the same plant
    if left == right:
        # Decide based on the rules: the one with more water, or Alice if equal
        if waterA >= waterB:
            if waterA < plants[left]:
                refills += 1
        else:
            if waterB < plants[left]:
                refills += 1

    return refills

# Example usage:
#print(minimumRefill([2,2,3,3], 5, 5))
← Back to All Questions