How hard is LeetCode 755. Pour Water?

LeetCode 755. Pour Water is rated Medium on LeetCode.

What is the time complexity of LeetCode 755. Pour Water?

The Python solution on this page runs in O(v \times n).

What is the space complexity of LeetCode 755. Pour Water?

The Python solution on this page uses O(1), where v and n are the number of water drops and the length of the height array, respectively auxiliary space.

What topics does LeetCode 755. Pour Water cover?

LeetCode 755. Pour Water is tagged Array and Simulation on LeetCode.

Is LeetCode 755. Pour Water a premium problem?

Yes. LeetCode 755. Pour Water is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Pour Water — LeetCode 755 Python Solution

MediumLeetCode PremiumArraySimulation

Problem: #755
Reading time: 4 min
Source: leetcode.com

The problem

You are given an elevation map represents as an integer array heights where heights[i] representing the height of the terrain at index i. The width at each index is 1.

Example

Input: heights = [2,1,1,2,1,2,2], volume = 4, k = 3
Output: [2,2,2,3,2,2,2]
Explanation: The first drop of water lands at index k = 3. When moving left or right, the water can only move to the same level or a lower level. (By level, we mean the total height of the terrain plus any water in that column.)

Python solution

Python

class Solution:
    def pourWater(self, heights: List[int], volume: int, k: int) -> List[int]:
        for _ in range(volume):
            for d in (-1, 1):
                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
                if j != k:
                    heights[j] += 1
                    break
            else:
                heights[k] += 1
        return heights

Complexity

Measure	Complexity
Time	O(v \times n)
Space	O(1), where v and n are the number of water drops and the length of the height array, respectively auxiliary

Frequently asked questions

How hard is LeetCode 755. Pour Water?: LeetCode 755. Pour Water is rated Medium on LeetCode.
What is the time complexity of LeetCode 755. Pour Water?: The Python solution on this page runs in O(v \times n).
What is the space complexity of LeetCode 755. Pour Water?: The Python solution on this page uses O(1), where v and n are the number of water drops and the length of the height array, respectively auxiliary space.
What topics does LeetCode 755. Pour Water cover?: LeetCode 755. Pour Water is tagged Array and Simulation on LeetCode.
Is LeetCode 755. Pour Water a premium problem?: Yes. LeetCode 755. Pour Water is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.