Why is My Python Solution For Trapped Rain Problem so slow?

Question

I have been working on the Leetcode version of the Trapped Rain Problem (See below). My solution passes almost all of the test cases, but I get a "Time Limit Exceeded" failure on test 318, which is just a very long input. I'm a noob, so can someone tell me what part of my solution has the biggest time cost? My code is after the problem description.

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5] Output: 9

Constraints:

n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105

Code:

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        volume = 0
        ceiling = 0
        for i in height:
            if i > ceiling:
                ceiling = i

        while ceiling > 0:
            list_of_peaks = []
            for i in range(0,len(height)):
                if height[i] >= ceiling:
                    list_of_peaks.append(i)
            for elem in range(0,len(list_of_peaks)):
                try:
                    volume = volume + (list_of_peaks[elem+1]-list_of_peaks[elem]-1)
                except:
                    break
            ceiling -= 1
        return volume

I have tried to identify what part of my solution is inefficient, but I am not experienced enough to identify what needs to be improved.

Answer 1

This is because the time complexity of your code is O(nm), where n is the number of elements in height, and m is the maximum value in height. In this case, n*m can reach at most 2*10^4*10^5 You should consider other algorithm, such as DP.

class Solution:
def trap(self, height: List[int]) -> int:
    if not height:
        return 0
    
    n = len(height)
    leftMax = [height[0]] + [0] * (n - 1)
    for i in range(1, n):
        leftMax[i] = max(leftMax[i - 1], height[i])

    rightMax = [0] * (n - 1) + [height[n - 1]]
    for i in range(n - 2, -1, -1):
        rightMax[i] = max(rightMax[i + 1], height[i])

    ans = sum(min(leftMax[i], rightMax[i]) - height[i] for i in range(n))
    return ans