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)
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
accumulate in particular is useful here:
class Solution(object): def runningSum(self, nums): return [*accumulate(nums)]