#Why does my code have such terrible time and space efficiency??

12 messages · Page 1 of 1 (latest)

mental zenith
#

it is because doing a lot of iteration, first it iterates through range() then it iterates through nums[0:i] and gets the sum of it, then iterates through nums[i+1:] and sums it

#

you could follow a better approach

#

instead get the sum of the whole list once, then have a variable left_sum = 0 ..eg and loop through range(0, len(sums)) and add to the left sum right_sum += nums[i] calculate right sum right_sum = total_sum - left_sum, if they are equal return the index otherwise continue

nova oracle
#

So you would have O(n) runtime and O(1) space

peak imp
#

This is called prefix sum by the way

#

or partial sum

nova oracle
#

O(1) since you don't count the size of args passed in

#

Your runtime is roughly n^2, accounting for the for loop and the in check

#

You can further optimize to make it O(n) by sacrificing a bit of space and using a dictionary

twin pumice
#

fyi dictionary is O(1) lookup

marsh cobalt
#

hashmap moment