Watering Plants

Medium

Asked by:

5 views

Topics:

ArraysGreedy Algorithms

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 i^th 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^th plant needs, and an integer capacity representing the watering can capacity, return the number of steps needed to water all the plants.

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] <= 10⁶
max(plants[i]) <= capacity <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the `plants` array contain non-positive values (zero or negative plant requirements)?
What are the upper and lower bounds for the capacity of the watering can?
If the watering can is empty at the start, do I still consider the starting point as a step?
If the capacity is sufficient to water all the plants without refilling, do I still need to return to the river?
If the `plants` array is empty, what should I return?

Brute Force Solution

Approach

The brute force approach to watering plants involves simulating every possible way you could water the plants. We repeatedly check if we have enough water, and if not, go back to refill, until all plants are watered. This method guarantees finding the answer but can be inefficient.

Here's how the algorithm would work step-by-step:

Start at the beginning, ready to water the first plant.
Check if you have enough water in your watering can to water the plant.
If you do, water the plant and move to the next plant.
If you don't have enough water, go back to refill your watering can completely.
Once refilled, return to the plant and water it.
Continue this process, going back to refill whenever needed, until all the plants are watered.
Count how many times you needed to refill your watering can.

Code Implementation

def watering_plants_brute_force(plants, capacity):
    steps = 0
    current_water = capacity
    plant_index = 0

    while plant_index < len(plants):
        # Check if we have enough water to water the current plant
        if current_water >= plants[plant_index]:
            current_water -= plants[plant_index]
            plant_index += 1
            steps += 1

        else:
            # We need to go back to refill
            steps += plant_index  

            # Refill the watering can
            current_water = capacity
            steps += plant_index + 1

            #Water the plant
            current_water -= plants[plant_index]
            plant_index += 1
    
    return steps

Big(O) Analysis

Time Complexity

O(n^2) – The algorithm iterates through the plants array of size n. In the worst-case scenario, for each plant, we might need to return to the river to refill the watering can. Refilling and returning to a plant effectively involves traversing back to the beginning of the array and then forward again. Therefore, for each of the 'n' plants, we might perform a traversal of up to 'n' steps (refill trip). This leads to a potential 'n' operations for each of the 'n' plants, approximating n * n operations in the worst case. Thus, the time complexity is O(n^2).

Space Complexity

O(1) – The provided algorithm operates directly on the input and uses only a fixed number of variables to keep track of the current water level and the number of refills. No additional data structures that scale with the number of plants (N) are used. Therefore, the space complexity is constant, regardless of the number of plants.

Optimal Solution

Approach

The most efficient way to water the plants involves simulating the watering process with a focus on minimizing trips back to the water source. We track how much water is currently in the watering can and only return for refills when necessary. This avoids unnecessary trips.

Here's how the algorithm would work step-by-step:

Imagine you're walking along the row of plants, carrying your watering can.
Start with a full watering can.
For each plant, check if you have enough water to water it.
If you do, water the plant and reduce the water in your can.
If you don't have enough water, walk back to the water source to refill.
Count that return trip as steps taken. Remember you have to walk back to where the plant is to then water it.
Refill your watering can completely.
Water the plant, reducing the water in your can.
Continue to the next plant, repeating these steps until all plants are watered.
The total number of steps taken (moving between plants and returning for refills) is the answer.

Code Implementation

def watering_plants(plants, capacity): 
    steps_taken = 0
    current_water = capacity
    number_of_plants = len(plants)

    for i in range(number_of_plants): 
        # Check if we have enough water to water the current plant
        if current_water >= plants[i]:
            current_water -= plants[i]
            steps_taken += 1

        # If not, return to the river, refill, and then water
        else:
            steps_taken += i # Walking back to refill

            # Account for the trip back to the beginning.
            steps_taken += i
            current_water = capacity

            # Water the plant after refilling
            current_water -= plants[i]
            steps_taken += 1

    return steps_taken

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each plant once, where n is the number of plants. For each plant, it performs a constant amount of work: checking water availability, watering (if possible), and potentially returning to refill. Refilling involves walking back to the water source and then back to the current plant, which is a constant-time operation for each plant. Therefore, the time complexity is directly proportional to the number of plants, resulting in O(n).

Space Complexity

O(1) – The algorithm uses a fixed number of variables to keep track of the current water in the can and the number of steps. No additional data structures, like arrays or hash maps, are created that scale with the number of plants (N). Therefore, the auxiliary space used is constant and independent of the input size N, resulting in O(1) space complexity.

Edge Cases

Case	How to Handle
Null or empty plants array	Return 0 steps immediately, as there are no plants to water.
Negative plant requirements	Treat negative plant requirements as invalid and throw an IllegalArgumentException.
Initial capacity is less than or equal to 0	Treat initial capacity as invalid and throw an IllegalArgumentException.
Initial capacity is sufficient to water all plants in a single pass	Return the number of plants, as only one pass is required.
A single plant requires more water than the capacity	Return -1 to indicate it's not possible to water all the plants.
Maximum integer values for plant needs and/or capacity leading to potential integer overflows	Use long instead of int for internal calculations of capacity and steps to prevent overflow.
Very large number of plants, affecting memory usage	The solution should be efficient in terms of space complexity, ideally O(1), to prevent memory issues.
Plants array contains zero requirement for some plants	The watering steps should increment as plants with zero water are visited, even if no water is used.

Null or empty plants array

How to Handle:

Return 0 steps immediately, as there are no plants to water.

Negative plant requirements

How to Handle:

Treat negative plant requirements as invalid and throw an IllegalArgumentException.

Initial capacity is less than or equal to 0

How to Handle:

Treat initial capacity as invalid and throw an IllegalArgumentException.

Initial capacity is sufficient to water all plants in a single pass

How to Handle:

Return the number of plants, as only one pass is required.

A single plant requires more water than the capacity

How to Handle:

Return -1 to indicate it's not possible to water all the plants.

Maximum integer values for plant needs and/or capacity leading to potential integer overflows

How to Handle:

Use long instead of int for internal calculations of capacity and steps to prevent overflow.

Very large number of plants, affecting memory usage

How to Handle:

The solution should be efficient in terms of space complexity, ideally O(1), to prevent memory issues.

Plants array contains zero requirement for some plants

How to Handle:

The watering steps should increment as plants with zero water are visited, even if no water is used.