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.
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