2105. Watering Plants II


Problem Description

Alice and Bob are watering plants numbered from 0 to n - 1 in a row. Each plant requires a specific amount of water. Alice starts watering from the left (plant 0) moving to the right, while Bob begins from the right (plant n - 1) moving to the left. Both Alice and Bob are equipped with a watering can which is initially full, and they start watering simultaneously.

The key rules for watering the plants are as follows:

  1. The time to water each plant is the same, regardless of the water needed.
  2. They can only water a plant if their can has enough water for the whole plant. If not, they refill their can instantly and then water the plant.
  3. If Alice and Bob meet at the same plant, the one with more water will water it. If they have the same amount, Alice does it.

The goal is to find out the total number of times Alice and Bob have to refill their watering cans in order to water all the plants.

The input to the problem is an array plants containing the amount of water each plant needs, and two integers, capacityA and capacityB, indicating the capacity of Alice's and Bob's watering cans, respectively.

Intuition

To solve this problem, we can simulate the process of watering the plants. Alice and Bob move towards each other from opposite ends of the row. They each water the plants according to their capacities. We track the remaining water in their cans after watering each plant. If a can doesn't have enough water to fully water the current plant:

  • We increment a counter representing the number of refills.
  • We refill the can, subtracting the water needed for the current plant from the full capacity.

We continue this process until Alice and Bob meet at the same plant or pass by each other, meaning all plants have been watered. At the moment they reach the same plant, we compare their remaining water and make a decision based on the rule.

The intuition behind this approach is to mimic the real-world actions Alice and Bob would take, updating values and counters as necessary. By simulating the watering process step by step, we avoid missing any cases where a refill might be necessary and ensure we account for every plant.

Learn more about Two Pointers patterns.

Solution Approach

The solution adopts a two-pointer approach, with one pointer (i) starting from the beginning of the array (Alice's side), and another pointer (j) starting from the end of the array (Bob's side). These pointers represent the current position of Alice and Bob, respectively. As they move toward each other, we calculate the number of refills needed based on the rules given.

To implement the solution, the following steps are followed:

  1. Initialize two variables a and b to represent the full capacities of Alice's and Bob's watering cans (capacityA and capacityB) as they'll be refilled to these values.

  2. Initialize the pointer i to 0 and j to len(plants) - 1.

  3. Initialize a counter ans to 0 for counting the total number of refills made by Alice and Bob.

  4. Use a while loop to iterate as long as i <= j (meaning Alice and Bob are not past each other):

    • Check if i == j, which means Alice and Bob are at the same plant.

      • If so, check if their can capacity (max(capacityA, capacityB)) is less than the water needed for this plant (plants[i]). If it is, increment the ans counter as this will require a refill.
      • Then break the loop as all plants have been watered.
    • For Alice:

      • If the current water (capacityA) is less than what the current plant needs (plants[i]), refill Alice's can and increment the ans counter.
      • Otherwise, reduce Alice's current water by the amount needed for the plant.
      • Move to the next plant by incrementing i.
    • For Bob (similar to Alice):

      • If Bob's current water (capacityB) is less than what the current plant needs (plants[j]), refill Bob's can and increment the ans counter.
      • Otherwise, reduce Bob's current water by the amount needed for the plant.
      • Move to the previous plant by decrementing j.
  5. After the while loop, return the ans counter which now holds the total number of refills required.

The two-pointer technique allows us to effectively simulate the action of both individuals as they meet in the middle, considering both directions simultaneously. This approach ensures that both capacities and refill requirements are checked at every step, thus finding the minimum number of refills needed to water all plants.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach using a small example:

Suppose we have an array plants = [1, 2, 4, 2, 3], and capacityA (Alice's can capacity) is 5, and capacityB (Bob's can capacity) is 6.

Here is a step-by-step walkthrough:

  • Initialize Alice's current water a = capacityA = 5 and Bob's current water b = capacityB = 6.
  • Initialize the pointers for Alice and Bob i = 0 and j = 4 respectively, pointing at the start and end of the plants array.
  • Initialize the number of refills counter ans = 0.

Start the while loop:

  • Step 1: Alice at i = 0, Bob at j = 4

    • Alice has enough water for plant 0 (needs 1 water), so capacityA = 5 - 1 = 4. No refills needed.
    • Bob has enough water for plant 4 (needs 3 water), so capacityB = 6 - 3 = 3. No refills needed.
    • Move Alice to i = 1 and Bob to j = 3.
  • Step 2: Alice at i = 1, Bob at j = 3

    • Alice has enough water for plant 1 (needs 2 water), so capacityA = 4 - 2 = 2. No refills needed.
    • Bob has enough water for plant 3 (needs 2 water), so capacityB = 3 - 2 = 1. No refills needed.
    • Move Alice to i = 2 and Bob to j = 2.
  • Step 3: Alice at i = 2, Bob at j = 2 (they meet at the same plant)

    • The current plant 2 requires 4 water.
    • Alice only has capacityA = 2, which is not enough. She refills her can and capacityA is now 5 - 4 = 1, and ans is incremented to 1.
    • Bob doesn't water since Alice has already watered the plant.
    • Since Alice and Bob meet at the same plant and have gone through all plants, the while loop ends.

The total number of refills ans is 1. Therefore, Alice and Bob needed to refill their cans only once combined to water all the plants.

Solution Implementation

1from typing import List
2
3class Solution:
4    def minimum_refill(self, plants: List[int], capacity_a: int, capacity_b: int) -> int:
5        # Funtion to calculate the minimum number of refills needed.
6      
7        i, j = 0, len(plants) - 1  # Initialize pointers for Alice and Bob respectively.
8        num_refills = 0  # Counter for the number of refills.
9        current_a, current_b = capacity_a, capacity_b  # Current water capacities for Alice and Bob.
10      
11        while i <= j:
12            if i == j:  # If Alice and Bob reach the same plant.
13                if max(current_a, current_b) < plants[i]:  # If both can't water the plant, one needs to refill.
14                    num_refills += 1
15                break
16          
17            # Alice waters the plants from the beginning.
18            if current_a < plants[i]:  # If Alice doesn't have enough water for the plant.
19                current_a = capacity_a - plants[i]  # Refill minus what is needed for the current plant.
20                num_refills += 1  # Increment refill counter.
21            else:
22                current_a -= plants[i]  # Subtract the amount of water used for the plant.
23          
24            # Bob waters the plants from the end.
25            if current_b < plants[j]:  # If Bob doesn't have enough water for the plant.
26                current_b = capacity_b - plants[j]  # Refill minus what is needed for the current plant.
27                num_refills += 1  # Increment refill counter.
28            else:
29                current_b -= plants[j]  # Subtract the amount of water used for the plant.
30          
31            i += 1  # Move Alice to the next plant.
32            j -= 1  # Move Bob to the previous plant.
33      
34        return num_refills  # Return the total number of refills needed.
35
36# Example usage:
37solution = Solution()
38print(solution.minimum_refill([2, 4, 5, 1, 2], 5, 7))  # Example input to test the function.
39
1class Solution {
2  
3    // Method to determine the number of refills needed to water all plants
4    public int minimumRefill(int[] plants, int capacityA, int capacityB) {
5        int leftIndex = 0; // Starting index for Alice
6        int rightIndex = plants.length - 1; // Starting index for Bob
7        int refills = 0; // Counter for the number of refills
8        int remainingA = capacityA; // Remaining water in Alice's can
9        int remainingB = capacityB; // Remaining water in Bob's can
10
11        // Loop through the plants while both pointers do not cross each other
12        while (leftIndex <= rightIndex) {
13          
14            // When both Alice and Bob reach the middle plant
15            if (leftIndex == rightIndex) {
16                // If the plant's needs exceed both capacities, a refill is needed
17                if (Math.max(remainingA, remainingB) < plants[leftIndex]) {
18                    refills++;
19                }
20                break; // We break since this is the last plant to consider
21            }
22          
23            // Watering the plant with Alice's can
24            if (remainingA < plants[leftIndex]) {
25                remainingA = capacityA - plants[leftIndex]; // Refill Alice's can and water the plant
26                refills++; // Increment refill counter for Alice
27            } else {
28                remainingA -= plants[leftIndex]; // Use existing water for the plant
29            }
30
31            // Watering the plant with Bob's can
32            if (remainingB < plants[rightIndex]) {
33                remainingB = capacityB - plants[rightIndex]; // Refill Bob's can and water the plant
34                refills++; // Increment refill counter for Bob
35            } else {
36                remainingB -= plants[rightIndex]; // Use existing water for the plant
37            }
38
39            // Move towards the middle plant
40            leftIndex++; 
41            rightIndex--;
42        }
43
44        // Return the total number of refills needed by both Alice and Bob
45        return refills;
46    }
47}
48
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    // Function calculates the minimum number of refills required to water all plants.
7    int minimumRefill(std::vector<int>& plants, int capacityA, int capacityB) {
8        int leftIndex = 0; // Starting from the leftmost plant
9        int rightIndex = plants.size() - 1; // Starting from the rightmost plant
10      
11        int refills = 0; // Counter for the number of refills
12        int remainingA = capacityA; // Remaining water in A's can
13        int remainingB = capacityB; // Remaining water in B's can
14      
15        // Water the plants from both ends until the paths of A and B meet or cross
16        while (leftIndex <= rightIndex) {
17            // Check if both A and B are at the same plant
18            if (leftIndex == rightIndex) {
19                // If the plant's requirement is higher than both A's and B's capacity, add a refill and end the loop
20                if (std::max(remainingA, remainingB) < plants[leftIndex]) {
21                    ++refills;
22                }
23                break;
24            }
25            // Watering from A's side
26            if (remainingA < plants[leftIndex]) {
27                remainingA = capacityA - plants[leftIndex]; // Refill A's can and use water for the current plant
28                ++refills; // Count the refill
29            } else {
30                remainingA -= plants[leftIndex]; // Deduct the water used for the current plant
31            }
32
33            // Watering from B's side
34            if (remainingB < plants[rightIndex]) {
35                remainingB = capacityB - plants[rightIndex]; // Refill B's can and use water for the current plant
36                ++refills; // Count the refill
37            } else {
38                remainingB -= plants[rightIndex]; // Deduct the water used for the current plant
39            }
40
41            ++leftIndex; // Move A to the next plant
42            --rightIndex; // Move B to the previous plant
43        }
44      
45        return refills; // Return the total number of refills required
46    }
47};
48
1// Define a function to calculate the minimum number of refills required to water all plants.
2function minimumRefill(plants: number[], capacityA: number, capacityB: number): number {
3    let leftIndex: number = 0; // Starting from the leftmost plant
4    let rightIndex: number = plants.length - 1; // Starting from the rightmost plant
5  
6    let refills: number = 0; // Counter for the number of refills
7    let remainingA: number = capacityA; // Remaining water in A's can
8    let remainingB: number = capacityB; // Remaining water in B's can
9  
10    // Water the plants from both ends until the paths of A and B meet or cross
11    while (leftIndex <= rightIndex) {
12        // Check if A and B are at the same plant
13        if (leftIndex === rightIndex) {
14            // If the plant's requirement is higher than both A's and B's remaining capacity, add a refill
15            if (Math.max(remainingA, remainingB) < plants[leftIndex]) {
16                refills++;
17            }
18            break;
19        }
20      
21        // Watering from A's side
22        if (remainingA < plants[leftIndex]) {
23            remainingA = capacityA; // Refill A's can
24            refills++; // Count the refill
25            remainingA -= plants[leftIndex]; // Use water for the current plant
26        } else {
27            remainingA -= plants[leftIndex]; // Deduct the water used for the current plant
28        }
29
30        // Watering from B's side
31        if (remainingB < plants[rightIndex]) {
32            remainingB = capacityB; // Refill B's can
33            refills++; // Count the refill
34            remainingB -= plants[rightIndex]; // Use water for the current plant
35        } else {
36            remainingB -= plants[rightIndex]; // Deduct the water used for the current plant
37        }
38
39        leftIndex++; // Move A to the next plant
40        rightIndex--; // Move B to the previous plant
41    }
42  
43    return refills; // Return the total number of refills required
44}
45
46// Variable and function usage example:
47
48// Capacity of watering cans for person A and B
49const capacityA: number = 5;
50const capacityB: number = 7;
51
52// Plants array where each element represents the amount of water required to water the plant
53const plants: number[] = [2, 4, 5, 1, 2, 3, 2, 3];
54
55// Calculate the minimum number of refills needed to water all plants
56const minRefills: number = minimumRefill(plants, capacityA, capacityB);
57
58console.log(minRefills); // Outputs the result
59

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(n), where n is the length of the plants list. This is because the code uses a single while loop to traverse the list from both ends towards the center, performing a constant number of calculations at each step. In the worst case, the loop runs for the entire length of the list if there's only one refill station (when i starts at 0 and j at n-1, incrementing and decrementing respectively until they meet), thus the time complexity is linear with respect to the number of plants.

Space Complexity

The space complexity of the code is O(1). This is because the code uses a fixed amount of extra space (variables to keep track of the positions i, j, the remaining capacities capacityA and capacityB, and the counter ans for the number of refills). This space requirement does not grow with the size of the input (plants list), hence the constant space complexity.

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

In a binary min heap, the maximum element can be found in:


Recommended Readings