Increasing speed of Sum of Pairs- Codewars

user_13505312 0
Viewed 192

I've just started learning to code around 2 weeks ago and have come across the below problem. I originally wrote the code as a double nested loop but that unsurprisingly timed out. I have recompiled my code in order to (I think) have an asymptotic run time of O(n) as opposed to O(n^2). I'm looking for ways to make my code faster: 

def sum_pairs(ints, s):
    minn = min(ints)
    if s < 0:
        minn +- s
    if minn > 0:
        minn = 0
    maxx = max(ints)
    if s > maxx:
        maxx = s
    ans = [0] * 2
    arr = [0.5] * (maxx-2*minn +1)
    for i in range (0, len(ints), 1):
        target = s - ints[i]
        if target >= minn:
            if not arr[target-minn] == 0.5:
                ans[0] = target
                ans[1] = ints[i]
                return ans
        arr[ints[i]-minn] = i
    return None

Problem

Given a list of integers and a single sum value, return the first two values (parse from the left please) in order of appearance that adds up to form the sum.

sum_pairs([11, 3, 7, 5], 10)

           ^--^      3 + 7 = 10

== [3, 7]

sum_pairs([4, 3, 2, 3, 4], 6)

       ^-----^         4 + 2 = 6, indices: 0, 2 *
          ^-----^      3 + 3 = 6, indices: 1, 3
             ^-----^   2 + 4 = 6, indices: 2, 4

* entire pair is earlier, and therefore is the correct answer == [4, 2]

https://www.codewars.com/kata/54d81488b981293527000c8f/train/python

sum python performance
1 Answers

Here is an approach that will get you linear execution time:

  • create a mapping that associates the index of the first occurrence of each array element.

  • then iterate on the array for each index/value:

    • if index is greater than the offset of the current best, break from the loop.
    • if the sum-value is in the array: if its offset is less than the current best, remember the pair.

  • at the end of this iteration, either there are no pairs or you have the first pair.

user_45932670
Related