Watch 3 video solutions for Watering Plants II, a medium level problem involving Array, Two Pointers, Simulation. This walkthrough by Programming Live with Larry has 274 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |