Problem Description

You have a terrain represented as an array heights where heights[i] is the height of the terrain at position i. Each position has a width of 1 unit. You need to pour volume units of water, one unit at a time, starting at position k.

When each unit of water is poured at position k, it follows these movement rules:

1. Try to move left: If the water can eventually fall to a lower level by moving left, it will flow left
2. Otherwise, try to move right: If the water can't fall left but can eventually fall to a lower level by moving right, it will flow right
3. Otherwise, stay: If the water can't fall in either direction, it accumulates at position k

The term "eventually fall" means the water will reach a position with a lower total level (terrain height + accumulated water) if it keeps moving in that direction. When water moves in a direction, it flows to the lowest reachable position in that direction.

Key constraints:

• The terrain extends infinitely high on both sides outside the array bounds (water cannot overflow the edges)
• Each unit of water must occupy exactly one position (no splitting across multiple positions)
• Water accumulates on top of terrain and previously poured water

The goal is to return the final state of the array after pouring all volume units of water, where each element represents the total height (original terrain + accumulated water) at that position.

For example, if heights = [2,1,1,2,1,2,2], volume = 4, and k = 3, the water poured at index 3 will flow and accumulate at the lower positions, resulting in the final configuration.

Intuition

The key insight is that we need to simulate each water drop individually because the placement of previous drops affects where the next drop will land. Each drop follows a predictable pattern: it tries to flow to the lowest reachable point.

When a water drop lands at position k, we need to explore both directions to find where it should settle. The critical observation is that water follows a greedy approach - it always prefers to move left over right (according to the problem rules), and it will flow to the lowest point it can reach in that direction.

For each direction, we can scan outward from position k and track two things:

1. Whether we can continue moving (the next position is not higher than our current position)
2. The lowest position we've encountered so far

The scanning process continues as long as heights[i + d] <= heights[i], meaning we can either move to the same level or drop down. During this scan, whenever we find a strictly lower position (heights[i + d] < heights[i]), we update our target position.

The elegant part of this solution is using a loop over directions d in (-1, 1) where -1 represents left and 1 represents right. By checking left first, we naturally implement the rule "if water can fall left, go left; otherwise try right." The for-else construct in Python perfectly handles the case where water can't fall in either direction - if we break out of the direction loop (water found a place to fall), the else block doesn't execute; if we complete both directions without breaking (water can't fall anywhere), the else block executes and places water at position k.

This simulation approach works because water behaves deterministically - given the same terrain configuration, a drop at position k will always end up in the same place. By processing drops one at a time and updating the heights array after each drop, we accurately model how the water accumulates and affects subsequent drops.

Solution Approach

The solution uses a simulation approach to process each unit of water individually. Here's how the implementation works:

Main Loop Structure:

for _ in range(volume):

We iterate volume times, processing one unit of water in each iteration.

Direction Exploration:

for d in (-1, 1):

For each water unit, we explore two directions: left (d = -1) and right (d = 1). By checking left first, we implement the rule that water prefers to flow left.

Scanning for the Lowest Point:

i = j = k
while 0 <= i + d < len(heights) and heights[i + d] <= heights[i]:
    if heights[i + d] < heights[i]:
        j = i + d
    i += d

• Initialize both i (current position) and j (target position) to k
• Continue scanning in direction d as long as:
  • We're within array bounds: 0 <= i + d < len(heights)
  • The next position is not higher: heights[i + d] <= heights[i]
• During the scan, if we find a strictly lower position (heights[i + d] < heights[i]), we update j to remember this as our target position
• Move to the next position: i += d

Water Placement Logic:

if j != k:
    heights[j] += 1
    break
else:
    heights[k] += 1

• If j != k, it means we found a lower position in the current direction, so we place water there and break out of the direction loop
• If we complete both directions without finding a place to drop (the for-else construct), water stays at position k

Time and Space Complexity:

• Time Complexity: O(volume × n) where n is the length of the heights array. For each unit of water, we potentially scan the entire array in the worst case.
• Space Complexity: O(1) as we only use a constant amount of extra space (variables i, j, d).

The beauty of this implementation is its simplicity - by processing water drops one at a time and always choosing the leftmost lowest point, we naturally implement all the problem's rules without complex logic or data structures.

Example Walkthrough

Let's walk through a small example with heights = [3, 1, 3], volume = 2, and k = 1 (pouring at the middle position).

Initial State:

Position: 0  1  2
Heights:  3  1  3

Pouring Unit 1:

• Start at position k=1 (height=1)
• Check left direction (d=-1):
  • Position 0 has height 3, which is higher than 1
  • Cannot move left (3 > 1), so j remains 1
• Check right direction (d=1):
  • Position 2 has height 3, which is higher than 1
  • Cannot move right (3 > 1), so j remains 1
• Since j=k=1 after checking both directions, water stays at position 1
• Update: heights[1] = 1 + 1 = 2

After Unit 1:

Position: 0  1  2
Heights:  3  2  3

Pouring Unit 2:

• Start at position k=1 (height=2 now)
• Check left direction (d=-1):
  • Position 0 has height 3, which is higher than 2
  • Cannot move left (3 > 2), so j remains 1
• Check right direction (d=1):
  • Position 2 has height 3, which is higher than 2
  • Cannot move right (3 > 2), so j remains 1
• Since j=k=1 after checking both directions, water stays at position 1
• Update: heights[1] = 2 + 1 = 3

Final State:

Position: 0  1  2
Heights:  3  3  3

The water filled up the valley at position 1, bringing it to the same level as its neighbors. This demonstrates how water accumulates when it cannot flow to a lower position in either direction.

Solution Implementation

Time and Space Complexity

Time Complexity: O(v × n)

For each water droplet (total v droplets), the algorithm searches for the lowest position where the water can settle. In the worst case, this search examines the entire array in both directions from position k. The inner while loop can iterate up to n positions (where n is the length of the heights array) for each direction. Since we process v water droplets and each droplet can potentially scan O(n) positions, the overall time complexity is O(v × n).

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space for variables i, j, and d, regardless of the input size. The modifications are made in-place to the input heights array, and no additional data structures that scale with input size are created. Therefore, the space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrect Handling of Equal Heights

The Problem: A common mistake is to stop scanning when encountering an equal height position, rather than continuing to look for a lower position beyond it. For example, with heights = [3, 1, 3, 1, 3] and water poured at index 2, some might incorrectly stop at index 1 (height 1) without checking index 0 (also height 1), missing that water should flow to the leftmost position of equal height.

Incorrect Implementation:

# WRONG: Stops at first non-increasing position
while 0 <= i + d < len(heights):
    if heights[i + d] < heights[i]:
        j = i + d
        break  # Wrong! Stops too early
    elif heights[i + d] == heights[i]:
        i += d
    else:
        break

Correct Solution: Continue scanning through equal heights to find the lowest reachable position:

while 0 <= i + d < len(heights) and heights[i + d] <= heights[i]:
    if heights[i + d] < heights[i]:
        j = i + d  # Update lowest, but keep scanning
    i += d

Pitfall 2: Not Understanding "Eventually Fall" Concept

The Problem: Some implementations only check the immediate neighbor instead of scanning until hitting a wall (higher position). For instance, with heights = [2, 2, 1, 2] and water at index 1, the water should "eventually fall" to index 2 by flowing over the equal height at index 1.

Incorrect Implementation:

# WRONG: Only checks immediate neighbor
if k > 0 and heights[k-1] < heights[k]:
    heights[k-1] += 1
elif k < len(heights)-1 and heights[k+1] < heights[k]:
    heights[k+1] += 1
else:
    heights[k] += 1

Correct Solution: Scan continuously in each direction until finding a higher wall or array boundary:

while 0 <= current_pos + direction < len(heights) and \
      heights[current_pos + direction] <= heights[current_pos]:
    # Keep scanning to find eventual fall position
    if heights[current_pos + direction] < heights[current_pos]:
        lowest_pos = current_pos + direction
    current_pos += direction

Pitfall 3: Modifying Heights During Scanning

The Problem: Updating the heights array while still determining where the current water unit should go can lead to incorrect decisions for subsequent scans within the same water unit placement.

Incorrect Implementation:

# WRONG: Modifying during scan affects decision making
for direction in (-1, 1):
    i = k
    while 0 <= i + direction < len(heights):
        if heights[i + direction] < heights[i]:
            heights[i + direction] += 1  # Wrong! Modified too early
            break
        i += direction

Correct Solution: Complete all scanning for the current water unit first, then modify the array only once after determining the final position:

for direction in (-1, 1):
    # First, find where water should go
    current_pos = k
    lowest_pos = k
    while 0 <= current_pos + direction < len(heights) and \
          heights[current_pos + direction] <= heights[current_pos]:
        if heights[current_pos + direction] < heights[current_pos]:
            lowest_pos = current_pos + direction
        current_pos += direction
  
    # Then, place the water
    if lowest_pos != k:
        heights[lowest_pos] += 1
        break
else:
    heights[k] += 1