Pour Water

Medium

Airbnb

7 views

Topics:

ArraysGreedy Algorithms

You are given the following to describe how much water pouring will affect a terrain. The terrain is represented as an array of non-negative integers, where each non-negative integer represents the height of a terrain block.

We will pour K units of water onto the terrain. The water will spread to the left and right only if there is a block lower than where the water is poured. We start pouring water at index index.

Return the array representing the terrain after pouring K units of water.

Example 1:

Input: heights = [2,1,1,2,1,2,2], K = 4, index = 3
Output: [2,2,2,3,2,2,2]
Explanation:
The first drop of water lands at index 3:
[2,1,1,2,1,2,2]
&x2192;[2,1,1,3,1,2,2].
The next drop of water lands at index 3:
[2,1,1,3,1,2,2]
&x2192;[2,1,1,4,1,2,2].
The next drop of water lands at index 3:
[2,1,1,4,1,2,2]
&x2192;[2,1,2,4,1,2,2].
The next drop of water lands at index 2:
[2,1,2,4,1,2,2]
&x2192;[2,1,3,4,1,2,2].

Example 2:

Input: heights = [1,2,3,4,3,2,1,2,3,2,1], K = 5, index = 5
Output: [1,2,3,4,3,3,2,2,3,2,1]

Example 3:

Input: heights = [1,2,2,2,2,1,1,2,1,2,1], K = 2, index = 5
Output: [1,2,2,2,2,2,2,2,1,2,1]

Constraints:

1 <= heights.length <= 100
0 <= heights[i] <= 100
1 <= K <= 1000
0 <= index < heights.length

Pour Water

Medium

Airbnb

7 views

Topics:

ArraysGreedy Algorithms

You are given the following to describe how much water pouring will affect a terrain. The terrain is represented as an array of non-negative integers, where each non-negative integer represents the height of a terrain block.

We will pour K units of water onto the terrain. The water will spread to the left and right only if there is a block lower than where the water is poured. We start pouring water at index index.

Return the array representing the terrain after pouring K units of water.

Example 1:

Input: heights = [2,1,1,2,1,2,2], K = 4, index = 3
Output: [2,2,2,3,2,2,2]
Explanation:
The first drop of water lands at index 3:
[2,1,1,2,1,2,2]
&x2192;[2,1,1,3,1,2,2].
The next drop of water lands at index 3:
[2,1,1,3,1,2,2]
&x2192;[2,1,1,4,1,2,2].
The next drop of water lands at index 3:
[2,1,1,4,1,2,2]
&x2192;[2,1,2,4,1,2,2].
The next drop of water lands at index 2:
[2,1,2,4,1,2,2]
&x2192;[2,1,3,4,1,2,2].

Example 2:

Input: heights = [1,2,3,4,3,2,1,2,3,2,1], K = 5, index = 5
Output: [1,2,3,4,3,3,2,2,3,2,1]

Example 3:

Input: heights = [1,2,2,2,2,1,1,2,1,2,1], K = 2, index = 5
Output: [1,2,2,2,2,2,2,2,1,2,1]

Constraints:

1 <= heights.length <= 100
0 <= heights[i] <= 100
1 <= K <= 1000
0 <= index < heights.length

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:

What is the data type of the heights? Are they integers or floating-point numbers?
What is the range of values for the heights, K, and V? Are negative values allowed?
If the water doesn't settle on any bucket (e.g., all surrounding buckets are higher), where should it go?
How should I handle the edge cases where K is at the very beginning or end of the height array?
If there are multiple locations with the same lowest height to pour water into, which one should I choose?

Brute Force Solution

Approach

The brute force approach to pouring water involves simulating the pouring process step by step. We'll directly simulate where the water flows after each drop is poured. This continues until all water has been poured.

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

Imagine each position where water can land as a container.
Start pouring one drop of water at the specified starting location.
Check if the water will flow to the left or the right by comparing the height of the container with its neighbors.
The water will flow to the lower neighbor. If both neighbors are taller, the water stays at the current position.
Pour the water into the lower neighbor's container, increasing its height.
Repeat the previous steps for each drop of water that needs to be poured.
Keep doing this until all the drops have been poured and each has settled in a container.
The resulting container heights represent the final water distribution.

Code Implementation

def pour_water(heights, water_amount, pour_location):
    heights = list(heights)

    for _ in range(water_amount):
        current_location = pour_location

        # Find the lowest adjacent index to move water to
        while True:
            left_index = current_location - 1
            right_index = current_location + 1

            # Check if left neighbor exists and is lower
            if left_index >= 0 and heights[left_index] < heights[current_location]:

                # Check if right neighbor is also lower than left neighbor, if so, skip to right
                if right_index < len(heights) and heights[right_index] < heights[left_index]:
                    break
                else:
                    current_location = left_index
                    continue

            # Check if right neighbor exists and is lower
            if right_index < len(heights) and heights[right_index] < heights[current_location]:
                current_location = right_index
                continue

            # No lower neighbor, water stays at the current location
            break

        # Increase the height at the final location
        heights[current_location] += 1

    return heights

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(V*N) – We pour V drops of water one by one. For each drop, we potentially iterate across the entire array of N heights to find the lowest adjacent container to which the water will flow. This means that for each of the V drops of water, we might perform up to N comparisons in the worst case to find the final resting place for that drop. Therefore, the overall time complexity is O(V*N), where V is the volume of water and N is the number of height positions.

Space Complexity

O(1) – The brute force approach, as described, modifies the input array (representing container heights) in place. It doesn't utilize any auxiliary data structures that scale with the input size. The algorithm only requires a few constant space variables to keep track of the current position and water height during the pouring simulation, irrespective of the input size N (the number of containers). Thus, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The problem asks us to simulate pouring water onto terrain represented by different heights. The trick is to efficiently figure out where the water will flow, instead of simulating every single drop individually. We'll focus on finding the lowest point near where we pour the water, and directing the water there.

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

Start at the location where the water is poured.
Check if the ground to the left is lower. If it is, move left and keep checking until you find a spot that's no longer lower than the spot to its left.
If you found a lower spot to the left, move all the water to that lowest spot.
If the ground to the left was never lower, then check if the ground to the right is lower. If it is, move right and keep checking until you find a spot that's no longer lower than the spot to its right.
If you found a lower spot to the right, move all the water to that lowest spot.
If neither left nor right has a lower spot, then the water stays where it was initially poured, and increase the height at that initial location.
Repeat this process for each drop of water.

Code Implementation

def pour_water(heights, water_amount, pour_location):    current_heights = heights[:]    for _ in range(water_amount):      current_location = pour_location      # Try to move water to the left.
      left_location = current_location      while left_location > 0 and current_heights[left_location - 1] <= current_heights[current_location]:        if current_heights[left_location - 1] < current_heights[current_location]:          current_location = left_location - 1
        else:
          left_location -= 1
      # If water didn't move left, try to move to the right.
      if current_location == pour_location:
        right_location = current_location
        while right_location < len(current_heights) - 1 and current_heights[right_location + 1] <= current_heights[current_location]:          if current_heights[right_location + 1] < current_heights[current_location]:            current_location = right_location + 1          else:            right_location += 1      # Water couldn't move; increase height at pour location
      if current_location == pour_location:        current_heights[pour_location] += 1      # Move water to the lowest spot found.
      else:        current_heights[current_location] += 1    return current_heights

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n*m) – For each of the 'm' drops of water, the algorithm potentially iterates through the height array to find the lowest point. In the worst case, for each drop, the algorithm might traverse the entire 'n' length height array twice - once to the left and once to the right. Therefore, the total number of operations can be approximated as m * 2n, where m is the number of water drops and n is the size of the height array. Thus, the time complexity simplifies to O(n*m).

Space Complexity

O(1) – The algorithm operates directly on the input height array without creating any auxiliary data structures that scale with the input size (N). It only uses a few constant space variables for tracking the current position of the water drop during the left or right descent to find the lowest point. Therefore, the space complexity is independent of the input size N, resulting in constant space.

Edge Cases

Case	How to Handle
Empty heights array	Return the original heights array unchanged if it's empty, as no water can be poured.
K is negative or larger than the array size	If K is invalid (negative or out of bounds), handle it by clamping it within the valid range [0, heights.length -1].
Drops is zero	If drops is zero, return the original array immediately, as no water needs to be poured.
Heights array contains very large values	Ensure integer overflow is handled during water accumulation by using a data type with sufficient range like long.
Heights array contains all identical values	The water should distribute evenly to the left or right depending on which direction offers the lowest point.
K is at the left or right edge of the array	The pouring will only distribute to the right or left, respectively.
Heights array contains negative values	Ensure negative height values are handled correctly, by considering them in the water distribution logic.
K is at the location of the tallest index	Water should flow left or right depending on which side has the shortest height.