Leetcode 2079: Watering Plants

Input: The input consists of an array `plants` where each element represents the amount of water a plant needs, and an integer `capacity` representing the watering can's capacity.

Example: [3, 3, 2, 4], capacity = 6

Constraints:

• 1 <= n <= 1000

• 1 <= plants[i] <= 10^6

• max(plants[i]) <= capacity <= 10^9

Output: Return the total number of steps required to water all the plants.

Example: For input [3, 3, 2, 4] and capacity 6, the output is 20.

Constraints:

Goal: Compute the total steps needed to water all the plants.

Steps:

• Start at the river with a full watering can.

• For each plant, check if there is enough water in the can. If not, return to the river to refill.

• Water the plant and subtract the required water from the can.

• Keep track of the total steps taken, including both watering steps and refill steps.

Goal: The solution must handle up to 1000 plants and ensure the watering can's capacity is large enough for the problem's constraints.

Steps:

• Array length is between 1 and 1000.

• Each plant requires between 1 and 10^6 units of water.

• Capacity is large enough to water at least one plant.

Assumptions:

• You will always have enough capacity to water the first plant.

• Input: Example 1

• Explanation: In this case, you water the plants, and whenever the watering can runs out, you return to the river to refill, taking the required steps each time.

• Input: Example 2

• Explanation: Here, the plants require a total of 16 steps to water all of them, including the refills.

Approach: The solution involves simulating the watering process, keeping track of the watering can's water level and the total steps taken.

Observations:

• A greedy approach works here where you water each plant and refill when necessary.

• The solution should iterate over the plants and simulate the watering process step-by-step.

Steps:

• Initialize the total steps as 0 and the current water level in the watering can as the capacity.

• For each plant, check if the watering can has enough water. If not, go back to the river to refill and track those steps.

• After watering a plant, decrease the water level accordingly and update the total steps.

Empty Inputs:

• The array will never be empty.

Large Inputs:

• The solution must work for up to 1000 plants efficiently.

Special Values:

• The plants array might contain very large numbers that require multiple refills.

Constraints:

• Ensure the solution handles the edge case where all plants require more water than the capacity of the watering can.

int wateringPlants(vector<int>& num, int cap) {
    int n = num.size();
    int rel = cap;
    int res = 0;
    for(int i = 0; i < n; i++) {
        if(num[i] > rel) {
            rel = cap;
            res += 2*i;
        } 
        rel -= num[i];            
    }
    return res + n;
}

1 : Function Declaration

int wateringPlants(vector<int>& num, int cap) {

This is the function declaration for `wateringPlants`, which accepts a vector `num` containing the water requirements of the plants and an integer `cap` representing the water can's capacity. It returns the total number of steps to water all plants.

2 : Variable Initialization

    int n = num.size();

This line initializes `n` to the size of the `num` vector, which represents the total number of plants.

3 : Variable Initialization

    int rel = cap;

This line initializes the variable `rel` to store the remaining water in the can, initially set to the full capacity `cap`.

4 : Variable Initialization

    int res = 0;

This line initializes a counter `res` to zero, which will track the total number of steps taken to water all the plants.

5 : For Loop

    for(int i = 0; i < n; i++) {

This `for` loop iterates through each plant in the `num` vector, where `i` is the index of the current plant.

6 : Conditional Check

        if(num[i] > rel) {

This condition checks if the remaining water `rel` is insufficient to water the current plant (`num[i]`). If true, the water can needs to be refilled.

7 : Water Can Refill

            rel = cap;

This line simulates refilling the water can by resetting `rel` to the full capacity `cap`.

8 : Step Calculation

            res += 2*i;

This adds `2 * i` steps to the total count `res`, since it requires `i` steps to walk to the water source and `i` steps to return to the current plant after refilling.

9 : Water Deduction

        rel -= num[i];

This line decreases the remaining water in the can by the amount needed to water the current plant.

10 : Final Step Calculation

    return res + n;

This line returns the total number of steps taken, including one step for each plant to water it.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is linear in relation to the number of plants, since each plant is processed once.

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is constant, as we only need a few variables to track the water level and steps.

Leetcode 2079: Watering Plants

Explore →