190.md

2079. Watering Plants

Difficulty: 🟡 Medium

You want to water n plants in your garden with a watering can. 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. 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 ith plant needs, and an integer capacity representing the watering can capacity, return the number of steps needed to water all the plants.

Examples:

Example 1:

Input: plants = [2,2,3,3], capacity = 5
Output: 14
Explanation: Start at the river with a full watering can:
- Walk to plant 0 (1 step) and water it. Watering can has 3 units of water.
- Walk to plant 1 (1 step) and water it. Watering can has 1 unit of water.
- Since you cannot completely water plant 2, walk back to the river to refill (2 steps).
- Walk to plant 2 (3 steps) and water it. Watering can has 2 units of water.
- Since you cannot completely water plant 3, walk back to the river to refill (3 steps).
- Walk to plant 3 (4 steps) and water it.
Steps needed = 1 + 1 + 2 + 3 + 3 + 4 = 14.

Example 2:

Input: plants = [1,1,1,4,2,3], capacity = 4
Output: 30
Explanation: Start at the river with a full watering can:
- Water plants 0, 1, and 2 (3 steps). Return to river (3 steps).
- Water plant 3 (4 steps). Return to river (4 steps).
- Water plant 4 (5 steps). Return to river (5 steps).
- Water plant 5 (6 steps).
Steps needed = 3 + 3 + 4 + 4 + 5 + 5 + 6 = 30.

Example 3:

Input: plants = [7,7,7,7,7,7,7], capacity = 8
Output: 49
Explanation: You have to refill before watering each plant.
Steps needed = 1 + 1 + 2 + 2 + 3 + 3 + 4 + 4 + 5 + 5 + 6 + 6 + 7 = 49.

Constraints:

• n == plants.length
• 1 <= n <= 1000
• 1 <= plants[i] <= 106
• max(plants[i]) <= capacity <= 109

Solutions

O(n) solution

Python3

class Solution:
    def wateringPlants(self, plants: List[int], capacity: int) -> int:
        bucket, total_steps = capacity, 0
        current_position, last_position = -1, len(plants)

        while current_position + 1 < last_position:
            current_position += 1 

            if plants[current_position] > bucket:
                bucket = capacity
                total_steps += current_position
                current_position = -1
                continue

            total_steps += 1
            if plants[current_position] <= bucket:
                bucket -= plants[current_position]
                plants[current_position] = 0

        return total_steps

The given solution provides an approach to minimize the number of steps needed to water all the plants.

Here is a step-by-step overview of the solution:

1. Initialize variables bucket to store the remaining capacity of the watering can and total_steps to count the total steps taken.
2. Initialize current_position to -1 (representing the river) and last_position to the number of plants.
3. While there are still plants to water (i.e., current_position + 1 < last_position), do the following:
   • Move to the next plant by incrementing current_position.
   • If the water required for the current plant is greater than the remaining capacity of the watering can (bucket), refill the watering can at the river and reset current_position to -1.
   • Update the total steps based on the position of the current plant.
   • Update the remaining capacity of the watering can.
4. Return the total steps taken to water all the plants.

Complexity Analysis

The time complexity for this solution is O(n), where n is the number of plants. We iterate through all the plants once.

The space complexity is O(1) as we use a constant amount of additional space.

Summary

The given solution provides an approach to minimize the number of steps needed to water all the plants in the garden. It iterates through the plants, refilling the watering can when needed, and counts the steps taken. The solution has a time complexity of O(n) and a space complexity of O(1), where n is the number of plants.

NB: If you want to get community points please suggest solutions in other languages as merge requests.