Pour Water - Leetcode Solution

The Pour Water problem on LeetCode is a problem where you have to simulate the pouring of water on a structure represented by an array. The problem statement is as follows:

You are given an array of non-negative integers representing the heights of blocks. The width of each block is 1. You have to pour water at some of the blocks. Each block can retain at most 1 unit of water. You have to simulate the pouring of water and return the final state of the structure.

The problem can be solved by simulating the pouring of water on the structure. To simulate the pouring of water, we can start at the highest block and pour water on it. If the block can hold the water, we add the water to the block and move on to the next block. If the block cannot hold the water, we move to the next block and pour water on it. We repeat this process until we have poured all the water.

To implement this strategy, we can use two pointers, i and j, to represent the left and right boundary of the structure. We can start at the highest block, which can be found using a linear scan of the array. Once we have found the highest block, we pour water on it and move the pointer i to the left and the pointer j to the right. If the current block is lower than the previous block, we pour water on it and move the pointer i or j accordingly. If the current block is higher than the previous block, we stop pouring water and start again from the highest block using the new boundary.

The code for the solution can be written as follows:

def pourWater(heights, water, position):
    n = len(heights)
    i = position
    while water > 0:
        # Move left
        while i > 0 and heights[i] >= heights[i-1]:
            i -= 1
        # Move right
        while i < n-1 and heights[i] >= heights[i+1]:
            i += 1
        # Pour water
        if heights[i] < heights[position]:
            heights[i] += 1
            water -= 1
        else:
            heights[position] += 1
            water -= 1
    return heights

The code takes an array heights, representing the structure, an integer water, representing the amount of water to be poured, and an integer position, representing the position where the water is to be poured. The code returns the final state of the structure after pouring the water.

The code uses two while loops to move the pointers i and j as described earlier. It then checks if the current block can hold water. If it can, the water is poured on the block. If it cannot hold water, the water is poured on the initial position. The code returns the final state of the structure after all the water has been poured.

The time complexity of the code is O(w*n), where w is the amount of water and n is the size of the array heights. The space complexity of the code is O(1), since we are modifying the input array in place.

1