Watering Plants II
Problem Description
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 ith 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 ith 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.
Examples
Input: plants = [2,2,3,3], capacityA = 5, capacityB = 5
Output: 1
Explanation:
- Initially, Alice and Bob have 5 units of water each in their watering cans.
- Alice waters plant 0, Bob waters plant 3.
- Alice and Bob now have 3 units and 2 units of water respectively.
- Alice has enough water for plant 1, so she waters it. Bob does not have enough water for plant 2, so he refills his can then waters it.
So, the total number of times they have to refill to water all the plants is 0 + 0 + 1 + 0 = 1.
Input: plants = [2,2,3,3], capacityA = 3, capacityB = 4
Output: 2
Explanation:
- Initially, Alice and Bob have 3 units and 4 units of water in their watering cans
respectively.
- Alice waters plant 0, Bob waters plant 3.
- Alice and Bob now have 1 unit of water each, and need to water plants 1 and 2 respectively.
- Since neither of them have enough water for their current plants, they refill their cans and then water the plants.
So, the total number of times they have to refill to water all the plants is 0 + 1 + 1 + 0 = 2.
Input: plants = [5], capacityA = 10, capacityB = 8
Output: 0
Explanation:
- There is only one plant.
- Alice's watering can has 10 units of water, whereas Bob's can has 8 units. Since Alice has more water in her can, she waters this plant.
So, the total number of times they have to refill is 0.
Constraints
- n == plants.length
- 1 <= n <= 10⁵
- 1 <= plants[i] <= 10⁶
- max(plants[i]) <= capacityA, capacityB <= 10⁹
Now that we clearly understand the problem and what we need to do, it’s time to simulate the entire process step by step and work towards building our solution. The goal is to ensure that every plant gets the water it needs while keeping track of refills for both Alice and Bob.
Approach
Intuition
Alice and Bob have a garden with several plants arranged in a straight line. Each plant needs a certain amount of water to grow. Alice starts watering from the leftmost plant, and Bob starts watering from the rightmost plant. They both move toward each other until all the plants are watered.
Just having a clear understanding of only this part gives a clue that we can use two pointers to perform the simulation. The pointer will act like a marker that will tell us where Alice and Bob are in the garden. One pointer will track the plant Alice is watering, starting from the left, and the other will track the plant Bob is watering, starting from the right. These two pointers help us follow Alice and Bob as they water the plants from both ends of the garden. They keep moving toward each other, getting closer until all the plants are watered.
The catch is that they have watering cans that can only hold a limited amount of water. If their watering can doesn’t have enough water to fully water the plant they are on, they need to refill their can before continuing. Refilling takes no time. We are supposed to figure out how many times they refilled their cans in total.
At every plant they reach, Alice or Bob asks themselves one simple question: Do I (Alice or Bob) have enough water to water this plant?
The answer to this question depends on how much water is in the can compared to the amount of water the plant needs. If the can has enough water, they will water the plant and move on to the next one. However, if the water in the can is not enough, they will first refill the can, then water the plant, and only then move forward. To keep track of how many times they refill the can, we can use a simple variable that counts each refill as it happens.
What we need to return is a simple integer count of refills and that problem is solved. Now what’s left is how in the core logic we decide the answer to the above question.
How in the core logic will we answer the above question?
To keep things simple, we just need to compare the amount of water required by the plant at the index Alice or Bob is currently on with the amount of water left in their respective cans. The value in the plants array at any index can be accessed easily, so that’s not an issue. To track how much water is left in Alice’s and Bob’s cans, we can use two separate variables—one for Alice and one for Bob. These variables will show the current water level in their cans. By comparing these variables with the value from the plants array, we can easily determine whether the answer is "Yes" or "No."
Once our answer is determined we simply shift our pointer to point to the next plant. Which is the index next to the index of Alice’s pointer and likewise the index previous to the index of Bob’s pointer.
Now the last thing we are left with is, that Alice and Bob moving toward each other might reach the same plant at the same time. This can only happen when there is an odd number of plants, and they both meet in the middle. Since the time it takes to water a plant is the same for both, they’ll only end up on the same plant when there is one middle plant left.
When they both reach the same plant, the one with more water left in their can should water it. If both have the same amount of water left, Alice will take care of the plant. This situation only happens once, and we can handle it once they both meet at the middle plant.
Example: plants = [1,2,1]
Here Alice will start from the left and water the plant at index 0 (she may need to refill or not it depends on the water in Alice's can but that is not our concern now).
Bob will start from right and water the plant at index 2 then Alice and Bob both will move forward and backward respectively and land upon index 1.
This shows Alice and Bob can only meet when n is odd and that too in the middle.
This situation can be handled easily at the end. If the total number of plants, n, is odd, Alice and Bob’s pointers will both reach the middle plant at the same time. On the other hand, if n is even, their pointers will simply cross each other without stopping at the same plant.
At this point, if n is odd then we just need to check whether the water left in either Alice’s or Bob's can is enough to water the middle plant. To do this, we compare the water remaining in both cans and take the larger amount. If this is still not enough to water the middle plant, we refill the can, increase our refill count by one, and water the plant.
Once this final step is done, we simply return the total number of refills. And with that, the process is complete!
Dry run
Input: plants = [2,3,3,4,2], capacityA = 4, capacityB = 5
Output: 3
Explanation:
- Initially, Alice and Bob have 4 and 5 units of water respectively.
- Alice waters plant 0, Bob waters plant 4.
- Alice and Bob now have 2 units and 3 units of water respectively.
- Alice does not have enough water for plant 1, so she refills and waters it left with 1 unit of water. Bob also does not have enough water for plant 2, so he refills his can then waters it then water left in his can is 1 unit
- Now Alice and Bob both land on plant 2 also both have 1 unit of water in their cans which is not enough, so Alice refills it and water the last plant..
So, the total number of times they have to refill to water all the plants is 0 + 1 + 1 + 1 + 0 = 3.
Initial State:
- n = 5 (number of plants)
- left = 0 (Alice starts at plant 0)
- right = 4 (Bob starts at plant 4)
- canA = 4 (Alice's initial water capacity)
- canB = 5 (Bob's initial water capacity)
- refills = 0 (number of refills starts at 0)
Dry Run:Step 1: left = 0, right = 4
- Alice (plant 0):
- plants[left] = 2
- Alice has canA = 4, which is sufficient to water plant 0.
- After watering: canA = canA - plants[left] = 4 - 2 = 2.
- Bob (plant 4):
- plants[right] = 2
- Bob has canB = 5, which is sufficient to water plant 4.
- After watering: canB = canB - plants[right] = 5 - 2 = 3.
- Move pointers: left = 1, right = 3.
Step 2: left = 1, right = 3
- Alice (plant 1):
- plants[left] = 3
- Alice has canA = 2, which is not sufficient to water plant 1.
- Alice refills: canA = capacityA = 4, refills = refills + 1 = 1.
- After watering: canA = canA - plants[left] = 4 - 3 = 1.
- Bob (plant 3):
- plants[right] = 4
- Bob has canB = 3, which is not sufficient to water plant 3.
- Bob refills: canB = capacityB = 5, refills = refills + 1 = 2.
- After watering: canB = canB - plants[right] = 5 - 4 = 1.
- Move pointers: left = 2, right = 2.
Step 3: left = 2, right = 2
- Alice and Bob meet at plant 2:
- plants[left] = 3.
- canA = 1, canB = 1.
- Both Alice and Bob have insufficient water.
- The larger of canA and canB is 1, which is still insufficient.
- Refill needed: refills = refills + 1 = 3.
Final State:
- left = 3, right = 2 (pointers crossed, loop ends).
- Total refills = 3.
Step to write code
Step 1: Initialize variables:
- left set to 0 which is a pointer for Alice's current plant.
- right set to n-1 which is a pointer for Bob's current plant.
- canA depicts the current water in Alice's can.
- canB depicts the current water in Bob's can.
- refills show the count of refills needed.
Step 2: Simulate watering:
- While left < right:
- Check if Alice has enough water for plant left:
- If not, refill her can and increase refills.
- Deduct the water required for the plant.
- Check if Bob has enough water for plant right:
- If not, refill his can and increase refills.
- Deduct the water required for the plant.
- Move left and right pointers closer.
Step 3: Handle the middle plant:
- If left == right (Alice and Bob meet at the same plant):
- Check if either Alice or Bob has enough water.
- If neither has enough, refill the can of whoever is watering it, and increment refills.
Step 4: Return the total refills.
Approach for All Languages
C++
class Solution {
public:
// Function to calculate the minimum number of refills required.
int minimumRefill(vector<int>& plants, int capacityA, int capacityB) {
// Get the number of plants.
int n = plants.size();
// Initialize pointers for Alice (left) and Bob (right).
int left = 0, right = n - 1;
// Amount of water in Alice's and Bob's cans.
int canA = capacityA, canB = capacityB;
// Counter to keep track of the number of refills.
int refills = 0;
// Process plants from both ends until pointers meet.
while (left < right) {
// If Alice doesn't have enough water to water the left plant, refill.
if (plants[left] > canA) {
canA = capacityA; // Refill Alice's can.
refills++; // Increment refill count.
}
// If Bob doesn't have enough water to water the right plant, refill.
if (plants[right] > canB) {
canB = capacityB; // Refill Bob's can.
refills++; // Increment refill count.
}
// Water the plants.
canA -= plants[left];
canB -= plants[right];
// Move the pointers inward.
left++;
right--;
}
// If there's one plant left in the middle, check if refilling is needed.
if (left == right) {
// If neither can water the plant, refill.
if (max(canA, canB) < plants[left]) {
refills++;
}
}
// Return the total number of refills.
return refills;
}
};Java
class Solution {
// Function to calculate the minimum number of refills required.
public int minimumRefill(int[] plants, int capacityA, int capacityB) {
// Get the number of plants.
int n = plants.length;
// Initialize pointers for Alice (left) and Bob (right).
int left = 0, right = n - 1;
// Amount of water in Alice's and Bob's cans.
int canA = capacityA, canB = capacityB;
// Counter to keep track of the number of refills.
int refills = 0;
// Process plants from both ends until pointers meet.
while (left < right) {
// If Alice doesn't have enough water to water the left plant, refill.
if (plants[left] > canA) {
canA = capacityA; // Refill Alice's can.
refills++; // Increment refill count.
}
// If Bob doesn't have enough water to water the right plant, refill.
if (plants[right] > canB) {
canB = capacityB; // Refill Bob's can.
refills++; // Increment refill count.
}
// Water the plants.
canA -= plants[left];
canB -= plants[right];
// Move the pointers inward.
left++;
right--;
}
// If there's one plant left in the middle, check if refilling is needed.
if (left == right) {
// If neither can water the plant, refill.
if (Math.max(canA, canB) < plants[left]) {
refills++;
}
}
// Return the total number of refills.
return refills;
}
}Python
class Solution:
# Function to calculate the minimum number of refills required.
def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:
# Get the number of plants.
n = len(plants)
# Initialize pointers for Alice (left) and Bob (right).
left, right = 0, n - 1
# Amount of water in Alice's and Bob's cans.
canA, canB = capacityA, capacityB
# Counter to keep track of the number of refills.
refills = 0
# Process plants from both ends until pointers meet.
while left < right:
# If Alice doesn't have enough water to water the left plant, refill.
if plants[left] > canA:
canA = capacityA # Refill Alice's can.
refills += 1 # Increment refill count.
# If Bob doesn't have enough water to water the right plant, refill.
if plants[right] > canB:
canB = capacityB # Refill Bob's can.
refills += 1 # Increment refill count.
# Water the plants.
canA -= plants[left]
canB -= plants[right]
# Move the pointers inward.
left += 1
right -= 1
# If there's one plant left in the middle, check if refilling is needed.
if left == right:
# If neither can water the plant, refill.
if max(canA, canB) < plants[left]:
refills += 1
# Return the total number of refills.
return refillsJavascript
/**
* @param {number[]} plants
* @param {number} capacityA
* @param {number} capacityB
* @return {number}
*/
var minimumRefill = function(plants, capacityA, capacityB) {
let n = plants.length; // Get the number of plants.
let left = 0, right = n - 1; // Pointers for Alice (left) and Bob (right).
let canA = capacityA, canB = capacityB; // Amount of water in Alice's and Bob's cans.
let refills = 0; // Counter to keep track of the number of refills.
// Process plants from both ends until pointers meet.
while (left < right) {
// If Alice doesn't have enough water to water the left plant, refill.
if (plants[left] > canA) {
canA = capacityA; // Refill Alice's can.
refills++; // Increment refill count.
}
// If Bob doesn't have enough water to water the right plant, refill.
if (plants[right] > canB) {
canB = capacityB; // Refill Bob's can.
refills++; // Increment refill count.
}
// Water the plants.
canA -= plants[left];
canB -= plants[right];
// Move the pointers inward.
left++;
right--;
}
// If there's one plant left in the middle, check if refilling is needed.
if (left === right) {
// If neither can water the plant, refill.
if (Math.max(canA, canB) < plants[left]) {
refills++;
}
}
// Return the total number of refills.
return refills;
};Time Complexity: O(n)
Loop Analysis
The loop runs while left < right:
- Each iteration involves:
- Alice watering plant plants[left] (or refilling and watering it if needed).
- Bob watering plant plants[right] (or refilling and watering it if needed).
- Both pointer updates (left++ and right--).
Since the loop continues until left >= right, it performs n / 2 iterations in the worst case, where every plant is processed once by Alice or Bob..
Complexity of Each Iteration
- Constant work is done in each iteration for both Alice and Bob:
- Checking if there is enough water.
- Refilling the can (if needed).
- Updating the remaining water after watering.
- Incrementing or decrementing the pointers.
- Each iteration is O(1).
Thus, the total complexity of the loop is O(n).
Middle Plant Check
If n is odd, there will be one middle plant where left == right. This involves:
- Comparing the remaining water in Alice's and Bob's cans to the water needed for the middle plant.
- At most one refill is needed.
This step is O(1).
Thus, the overall time complexity of the algorithm is: O(n).
Space Complexity: O(1)
Auxiliary Space Complexity
Auxiliary space refers to the extra space or temporary space allocated by the algorithm during its execution (excluding the input data).
In the given code:
- Variables used:
- n: Stores the size of the input array plants.
- left, right: Two pointers to traverse the array.
- canA, canB: Represent Alice's and Bob's remaining water in their cans.
- refills: Keeps track of the number of refills.
- Operations:
- Simple arithmetic, comparisons, and pointer updates are all done in constant space.
The algorithm does not use any data structures (like arrays, stacks, or recursion) that would require additional memory.
Hence, the auxiliary space complexity is O(1) (constant space).
Total Space Complexity
The plants array and capacity of cans of Alice and Bob is passed as input, and its size is O(n), O(1), O(1) respectively where n is the number of plants. The array is not modified or copied, so no extra memory is consumed for the input.
The total space complexity is the sum of the space used by:
- Input space: The memory taken by the input array plants. This is O(n).
- Auxiliary space: Additional space used by the algorithm, which is O(1).
Thus, the total space complexity is: O(n) + O(1) = O(n).
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems:-
You want to water n plants in your garden with a watering can. The plants are arranged in a row and are labelled from 0 to n - 1 from left to right where the iᵗʰ 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 iᵗʰ plant needs, and an integer capacity representing the watering can capacity, return the number of steps needed to water all the plants.
There is a one-dimensional garden on the x-axis. The garden starts at the point 0 and ends at the point n. (i.e., the length of the garden is n).
There are n + 1 taps located at points [0, 1, ..., n] in the garden.
Given an integer n and an integer array ranges of length n + 1 where ranges[i] (0-indexed) means the iᵗʰ tap can water the area [i - ranges[i], i + ranges[i]] if it was open.
Return the minimum number of taps that should be open to water the whole garden, If the garden cannot be watered return -1.