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:
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.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.
Example 1:
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.
Example 2:
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.
Example 3:
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.length1 <= n <= 1051 <= plants[i] <= 106max(plants[i]) <= capacityA, capacityB <= 109Problem Overview: An array plants represents the water required for each plant in a row. Alice starts watering from the left and Bob from the right, each with their own watering can capacity. When either person doesn’t have enough water for the next plant, they refill. The goal is to simulate the process and return the total number of refills needed.
Approach 1: Sequential Simulation with Special Handling (O(n) time, O(1) space)
Simulate the watering process step by step while tracking the remaining water for Alice and Bob. Alice moves left to right and Bob moves right to left. Before watering a plant, check if the remaining water is enough; if not, increment the refill counter and reset the water level to full capacity. The only special case occurs when both pointers reach the same plant. At that point, the person with more remaining water handles the plant; if neither has enough, one final refill is required. This approach mirrors the real-world process directly and keeps the logic easy to follow.
Approach 2: Two Pointer Technique (O(n) time, O(1) space)
Use two pointers: left starting at index 0 and right starting at n-1. Maintain two variables tracking Alice’s and Bob’s remaining water. On each step, process the plant at left for Alice and the plant at right for Bob, refilling whenever the remaining capacity is insufficient. After watering, move the pointers inward. When left == right, only one plant remains; whichever person has more water attempts it, and if both have insufficient water, count one extra refill. The key insight is that both workers operate independently until the pointers meet, making a two-pointer simulation a natural fit.
The algorithm scans the array once while maintaining constant state variables, so the complexity stays linear. No additional data structures are required beyond counters and remaining capacity variables.
Conceptually, the problem is a clean example of two pointers combined with straightforward simulation on an array. Many interview questions use the same pattern: process elements from both ends while maintaining independent state.
Recommended for interviews: The two pointer approach is what interviewers typically expect. It demonstrates that you can model two independent processes moving toward each other and handle the meeting point correctly. A straightforward simulation still works, but recognizing the two-pointer structure signals stronger algorithmic intuition.
In this approach, we utilize the two-pointer technique to handle the problem efficiently. Alice and Bob can be visualized as pointers starting at opposite ends of the array and moving towards each other. We keep track of their current water levels and refill when necessary as per the problem's conditions. We handle the case where both may try to water the same plant by checking their water levels and deciding accordingly.
The above C code implements the two-pointer technique to calculate the number of refills required. It checks if Alice and Bob need to refill their cans before watering each plant and updates the refills count accordingly. It handles the case where both reach the same plant by comparing their water levels and deciding who waters it.
Time Complexity: O(n), where n is the number of plants. The solution involves a single traversal of the plant array.
Space Complexity: O(1), as we're only using a fixed amount of additional space.
In this method, we simulate the process step-by-step, with special handling when both pointers are on the same plant. We track the refill operations for each character individually and decide who waters the plant at their meeting point using their current water levels.
This C code focuses on processing the watering from both ends and uses an if-conditional check to handle the case when both Alice and Bob meet at the same plant. It tracks the refills separately for Alice and Bob.
Time Complexity: O(n) because the traversal covers each plant once.
Space Complexity: O(1) as it uses fixed storage variables.
We use two variables a and b to represent the amount of water Alice and Bob have, initially a = capacityA, b = capacityB. Then we use two pointers i and j to point to the head and tail of the plant array, and simulate the process of Alice and Bob watering from both ends to the middle.
When i < j, we judge whether Alice and Bob have enough water to water the plants. If not, we refill the watering cans. Then we update the amount of water a and b, and move the pointers i and j. Finally, we need to judge whether i and j are equal. If they are equal, we need to judge whether max(a, b) is less than the amount of water the plant needs. If it is less, we need to refill the watering cans again.
The time complexity is O(n), where n is the length of the plant array. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Two Pointer Technique | Time Complexity: O(n), where n is the number of plants. The solution involves a single traversal of the plant array. |
| Sequential Simulation with Special Handling | Time Complexity: O(n) because the traversal covers each plant once. |
| Two Pointers + Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sequential Simulation with Special Handling | O(n) | O(1) | When implementing the process exactly as described with explicit refill checks for Alice and Bob |
| Two Pointer Technique | O(n) | O(1) | Best general solution when processing elements from both ends of an array simultaneously |
2015. Watering Plants II (Leetcode Medium) • Programming Live with Larry • 274 views views
Watch 2 more video solutions →Practice Watering Plants II with our built-in code editor and test cases.
Practice on FleetCode