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

Answer 2

Here are some pointers:

• Do not use list.count() or list.index() (that is, try to remove local_map.count(1), local_map.index(1) and reversed_list.index(1)). The first will loop (internally) over the whole list, which is obviously expensive if the list is large. The second will loop over the list until a 1 is found. Currently you even have two calls to local_map.count(1) which will always return the same answer, so at least just store the result in a variable. In your loop over blocks, you construct local_map yourself, so you do in fact know exactly what it contains, you should not have to search through it afterwards. Just put a few ifs into the first loop over blocks.
• The operation local_map[::-1] not only runs over the whole list, but additionally copies the whole thing into a new list (backwards, but that's not really contributing to the issue). Again, this new list does not contain new information, so you can figure out the value of water_count without doing this.
• The above is really the major issues. A slight further optimization can be obtained by eliminating element = element + 1. Just shift the range, as in range(1, max_height + 1).
• Also, as written in the comments, prefer list.append(x) to list.extend([x]). It's not huge, but the latter has to create an additional list (of length 1), put x into it, loop over the list and append its elements (just x) to the large list. Finally, the length-1 list is thrown away. On the contrary, list.append(x) just appends x to the list, no temporary length-1 list needed.

Note that list.append() is not slow. It's a function call, which is always somewhat slow, but the actual data operation is fast: constant time and even cleverly amortized, as juanpa.arrivillaga writes.

Answer 3

Here's another way of looking at the problem. This scans left to right over the bins, and at each point, I track how many units of water are dammed up at each level. When there's a tall wall, we tally up whatever units it was damming, and clear them. However, this still gets an "overtime" flag on the next to the last test, which has about 10,000 entries. It takes 20 seconds on my relatively old box.

class Solution():
    def trap(self, height):
        trapped = 0
        accum = [0]*max(height)
        lastwall = -1

        for h in height:
            # Take credit for everything up to our height.
            trapped += sum(accum[0:h])
            accum[0:h] = [0]*h
            for v in range(h,lastwall):
                accum[v] += 1
            lastwall = max(lastwall,h)

        return trapped

print(Solution().trap([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
print(Solution().trap([4,2,0,3,2,5])) # 9