Is appending element faster than replacing in Python?

I got my first problem handed to me on leet code which was about making a Fibonacci sequence function. This was my submission below. As some of you may notice I come from MATLAB background and I think they always define a matrix first.

I looked at other solutions after solving this and noticed that most of fast solution went for appending. Mine wasn’t slow but I was curious. As my title suggests is it more efficient to append in Python?

class Solution(object):
    def runningSum(self, nums):

        newnums=nums[0:]

        for i in range(len(nums)):
            newnums[i]=sum(nums[:i+1])

        return(newnums)

>Solution :

For a long list whose length is known in advance, it should be somewhat beneficial to create the list first (as you do), because the repeated appending will have to resize and copy the underlying array every now and then.
What makes your approach quadratic is the repeated summing of the entire list prefix when you have the previous sum readily available in the previous cell of your result:

class Solution(object):
    def runningSum(self, nums):
        newnums = nums[:]  # shallow copy
        for i in range(1, len(nums)):
            newnums[i] += newnums[i-1]  # just add prev cell
        return newnums

Also, Leetcode is usually quite liberal with modifying their input data. They don’t check if you mutate them, so even the simpler

class Solution(object):
    def runningSum(self, nums):
        for i in range(1, len(nums)):
            nums[i] += nums[i-1]  # just add prev cell
        return nums

works. Both are linear in time complexity but you save the effort of creating a new list. And once you get into Leetcode specifics, you can make use of the fact that they have all the itertools imported, accumulate in particular is useful here:

class Solution(object):
    def runningSum(self, nums):
        return [*accumulate(nums)]

Leave a Reply