Python how do i make list appends / extends quicker?

Question

Heyo all.

Trying to get better at python and started doing leetcode problems. Im currently doing one, were the goal is to capture water. Link => https://leetcode.com/problems/trapping-rain-water/

problem is; it times me out for taking too long. My code is certainly inefficient. Afer googling around i found that .append is supposedly very slow / inefficient. So is .extend.

Cant find any obvious ways of making my code faster; hence my arrival here.

any response is much appreciated

class Solution:
    def trap(self, height: List[int]) -> int:
        
        max_height = max(height)
        water_blocks = 0
        for element in range(max_height):
            local_map = []
            element = element + 1
            for block in height:
                if block >= element:
                    local_map.extend([1])
                else:
                    local_map.extend([0])

            if local_map.count(1) > 1:
                first_index = local_map.index(1)
                reversed_list = local_map[::-1]
                last_index = len(local_map) - 1 - reversed_list.index(1)
                water_count = last_index - first_index - 1 - (local_map.count(1) - 2)
                water_blocks += water_count
            else:
                continue
        return water_blocks

Answer 1

Although many of your count and index calls can be avoided, the two big nested loops might still be a problem. For the outer loop, max_height can be large number and the inner loop iterates over the full list. You might need to come up with a different algorithm.

I don't have a leetcode account, so I can't really test my code, but this would be my suggestion: It iterates over the height-list only once, with a small inner loop to find the next matching wall.

class Solution:
    def trap(self, h):
        water = 0
        current_height = 0
        for i, n in enumerate(h):
            # found a "bucket", add water
            if n < current_height:
                water += current_height - n
            else: # found a wall. calculate usable height
                current_height = self.n_or_max(h[i+1:], n)
        return water

    def n_or_max(self, h, n):
        local_max = 0
        for i in h:
            if i > local_max:
                local_max = i
                # that's high enough, return n
                if i >= n:
                    return n
        return local_max