leetcode-755 Pour Water

# You are given an elevation map represented as an array of integers, where
# each integer represents the height at that position. Water is dropped at
# position K. Simulate water flowing and settling according to these rules:
#
# 1. Water first tries to flow left (to lower or equal ground)
# 2. If no lower ground on left, water tries to flow right
# 3. If no lower ground on either side, water stays at drop position
# 4. Water settles at the first position it can't fall further
#
# Example 1:
# Input: heights = [2,1,1,2,1,2,2], V = 4, K = 3
# Output: [2,2,2,3,2,2,2]
# Explanation:
# Drop 1: Water drops at index 3, flows left to index 2, settles at index 1
# Drop 2: Water drops at index 3, settles at index 2
# Drop 3: Water drops at index 3, settles at index 3
# Drop 4: Water drops at index 3, flows right to index 4, settles there
#
# Example 2:
# Input: heights = [1,2,3,4], V = 2, K = 2
# Output: [2,2,3,4]
#
# Constraints:
# 1 <= heights.length <= 100
# 0 <= heights[i] <= 99
# 0 <= V <= 2000
# 0 <= K < heights.length

class Solution:
    def pourWater(self, heights: List[int], V: int, K: int) -> List[int]:
        def drop_water(drop_idx):
            # Try to flow left
            best = drop_idx
            for i in range(drop_idx - 1, -1, -1):
                if heights[i] > heights[best]:
                    # Hit a wall, can't continue left
                    break
                if heights[i] < heights[best]:
                    # Found lower ground
                    best = i

            # If water settled on left, return
            if best < drop_idx:
                heights[best] += 1
                return

            # Try to flow right
            best = drop_idx
            for i in range(drop_idx + 1, len(heights)):
                if heights[i] > heights[best]:
                    # Hit a wall, can't continue right
                    break
                if heights[i] < heights[best]:
                    # Found lower ground
                    best = i

            # Settle at best position (could be drop_idx if nowhere to go)
            heights[best] += 1

        # Drop V units of water
        for _ in range(V):
            drop_water(K)

        return heights

# Time Complexity: O(V * n) where V is water units, n is array length
# Space Complexity: O(1) - modify in place
#
# Algorithm:
# For each water drop:
# 1. Check left side for lower ground (greedy - take first lower position)
# 2. If found, settle there
# 3. If not, check right side for lower ground
# 4. If found, settle there
# 5. If neither side has lower ground, stay at drop position
#
# Key Insight: Water flows greedily to first lower position
# - Left has priority over right
# - Stop when hitting higher ground (wall)
# - Settle at first position where water can't fall further
#
# AirBnB: Tests simulation and attention to detail
# Similar to real-world physics simulation problems