Watering Plants II - Practice Coding Problems

Watering Plants II - Problem

Alice and Bob want to water n plants in their garden. The plants are arranged in a row and are labeled from 0 to n - 1 from left to right where the i-th plant is located at x = i.

Each plant needs a specific amount of water. Alice and Bob have a watering can each, initially full. They water the plants in the following way:

Alice waters the plants in order from left to right, starting from the 0th plant. Bob waters the plants in order from right to left, starting from the (n - 1)th plant. They begin watering the plants simultaneously.
It takes the same amount of time to water each plant regardless of how much water it needs.
Alice/Bob must water the plant if they have enough in their can to fully water it. Otherwise, they first refill their can (instantaneously) then water the plant.
In case both Alice and Bob reach the same plant, the one with more water currently in his/her watering can should water this plant. If they have the same amount of water, then Alice should water this plant.

Given a 0-indexed integer array plants of n integers, where plants[i] is the amount of water the i-th plant needs, and two integers capacityA and capacityB representing the capacities of Alice's and Bob's watering cans respectively, return the number of times they have to refill to water all the plants.

Input & Output

Example 1 — Basic Case

$ Input: plants = [2,1,1,3], capacityA = 4, capacityB = 4

› Output: 2

💡 Note: Alice waters plants 0,1 (uses 3 water, has 1 left). Bob waters plant 3 (needs refill: 1 < 3), then plant 2. Total refills: 1 (Bob) + 1 (Alice for next round if needed) = 2

Example 2 — No Refills Needed

$ Input: plants = [1,1,1,1], capacityA = 4, capacityB = 4

› Output: 0

💡 Note: Alice waters plants 0,1 (uses 2 water). Bob waters plants 3,2 (uses 2 water). No refills needed.

Example 3 — Odd Length Collision

$ Input: plants = [5], capacityA = 3, capacityB = 4

› Output: 1

💡 Note: Both reach plant 0. Bob has more water (4 > 3), but 4 < 5, so Bob refills once to water the plant.

Constraints

n == plants.length
1 ≤ n ≤ 10⁵
1 ≤ plants[i] ≤ 10⁶
plants[i] ≤ capacityA, capacityB ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array of plant water needs and two watering can capacities

Process

Alice moves left→right, Bob moves right→left, both refill when needed

Output

Total number of refills required

Key Takeaway

🎯 Key Insight: Use two pointers to simulate Alice and Bob's convergent movement efficiently

Asked in

a Amazon 12 G Google 8 M Microsoft 6 f Meta 4

The key insight is to use two pointers representing Alice and Bob moving toward each other from opposite ends. The optimal approach uses two pointers technique to simulate their movement in O(n) time with careful handling of the collision case. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(n)	O(1)	Simulate each step of the watering process explicitly
Two Pointers Optimal	O(n)	O(1)	Use two pointers moving toward each other to simulate Alice and Bob

Brute Force Simulation — Algorithm Steps

Step 1: Initialize positions and water levels
Step 2: Simulate each time step until all plants watered
Step 3: Count total refills

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set Alice at position 0, Bob at position n-1, both with full cans

Simulate

Move step by step, refill when needed

Count

Return total refills needed

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* plants, int plantsSize, int capacityA, int capacityB) {
    int alicePos = 0;
    int bobPos = plantsSize - 1;
    int aliceWater = capacityA;
    int bobWater = capacityB;
    int refills = 0;
    
    while (alicePos <= bobPos) {
        if (alicePos == bobPos) {
            // Both reach the same plant
            if (aliceWater >= bobWater) {
                if (aliceWater < plants[alicePos]) {
                    refills++;
                    aliceWater = capacityA;
                }
                aliceWater -= plants[alicePos];
            } else {
                if (bobWater < plants[bobPos]) {
                    refills++;
                    bobWater = capacityB;
                }
                bobWater -= plants[bobPos];
            }
            break;
        }
        
        // Alice waters her plant
        if (aliceWater < plants[alicePos]) {
            refills++;
            aliceWater = capacityA;
        }
        aliceWater -= plants[alicePos];
        alicePos++;
        
        // Bob waters his plant
        if (bobWater < plants[bobPos]) {
            refills++;
            bobWater = capacityB;
        }
        bobWater -= plants[bobPos];
        bobPos--;
    }
    
    return refills;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int plants[100];
    int plantsSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        plants[plantsSize++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    int capacityA, capacityB;
    scanf("%d", &capacityA);
    scanf("%d", &capacityB);
    
    int result = solution(plants, plantsSize, capacityA, capacityB);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through all plants with constant work per plant

✓ Linear Growth

Space Complexity

O(1)

Only tracking positions, water levels, and refill counts

✓ Linear Space

28.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler