11.19.21

Codewars kata : Sum of pairs

This simple problem of finding a pair of numbers in a list of random integers, which adds up to a specific number, is easy to get working, but hard to optimize. So we will go through the various implementation strategies and see it metamorph to the final accepted version.

Implementation iterations

1. Maintain a cache of the left number seen. If that number has not generated a pass in the past ignore it. Also maintain an array of left , right indexes which have generated the result. This got the basic tests running, but the final submission timed out.

2. Maintain no cache of previously seen numbers, also maintain a tuple of (left index, right index, gap between two indices). Only if the gap is less for a new no# then overwrite the old entry. It iterates through the whole list hence not a great idea.

3. No need of cache, search only till the new idx + gap indexes, as any further we will get a pair which is farther away. Again as all the indices are being searched not an runtime efficient option.

def sum_pairs(ints, s):
    # startidx, endidx, gap
    nearest_pair = ()
    ints_len = len(ints)
    for i in range(ints_len):
        diff_s = s - ints[i]
        try:
            end_idx = ints_len
            if nearest_pair and nearest_pair[2] < ints_len:
                end_idx = i + nearest_pair[2]
            idx =  ints.index(diff_s, i+1, end_idx)
            gap = idx - i
            if not nearest_pair or (nearest_pair[2] > gap):
                nearest_pair = (i,idx, gap)
        except :
            pass
        if nearest_pair and nearest_pair[2] == 1:
            break

    if not nearest_pair:
        return None
    else:
        # sort the cache by start index & gap between indices
        return [ints[nearest_pair[0]], ints[nearest_pair[1]]]

4. We need to find the first two entries only, and then just return the one which is earlier. In worst case its O(n^2), but in best case it will be O(2n) only. But the codewars bot says its still too long running.

def sum_pairs(ints, s):
    # startidx, endidx, gap
    tuples_list = []
    ints_len = len(ints)
    for i in range(ints_len):
        diff_s = s - ints[i]
        end_idx = ints_len
        if tuples_list:
            end_idx = tuples_list[0][1]
        for z in range(i + 1, end_idx):
            if ints[z] == diff_s:
                tuples_list.append((i, z))
                break
        if len(tuples_list) == 2:
            if tuples_list[0][1] > tuples_list[1][1]:
                return [ints[tuples_list[1][0]],ints[tuples_list[1][1]]]
            return [ints[tuples_list[0][0]],ints[tuples_list[0][1]]]

5. My accepted solution#1: This involves using a cache to note numbers that have not generated any result. Then the same can be used to skip iterations. The worst case we will have O(n^2) with additional n entries needed for storage. Not too elegant, lots of verbose coding style.

def sum_pairs(ints, s):
    # startidx, endidx, gap
    tuples_list = []
    nums_cache = []
    ints_len = len(ints)
    for i in range(ints_len):
        if ints[i] in nums_cache:
            continue
        diff_s = s - ints[i]
        end_idx = ints_len
        if tuples_list:
            end_idx = tuples_list[0][1]
        num_seen = False
        for z in range(i + 1, end_idx):
            if ints[z] == diff_s:
                tuples_list.append((i, z))
                num_seen = True
                break
        if not num_seen:
            nums_cache.append(ints[i])
            continue
        if len(tuples_list) == 2:
            fe = tuples_list[0]
            se = tuples_list[1]
            if fe[1] > se[1]:
                return [ints[se[0]],ints[se[1]]]
            return [ints[fe[0]],ints[fe[1]]]


    if not tuples_list:
        return None
    if len(tuples_list) == 1:
        return [ints[tuples_list[0][0]],ints[tuples_list[0][1]]]

6. My accepted solution#2: I got a good use of for else and was able to shave off a few more milliseconds. This version adopts a more pythonic style.

def sum_pairs(ints, s):
    # startidx, endidx, gap
    tuples_list = []
    nums_cache = []
    ints_len = len(ints)
    for i in range(ints_len):
        if ints[i] in nums_cache:
            continue
        diff_s = s - ints[i]
        end_idx = ints_len if not tuples_list else tuples_list[0][1]
        for z in range(i + 1, end_idx):
            if ints[z] == diff_s:
                tuples_list.append((i, z))
                break
        else:
            nums_cache.append(ints[i])
                
        if len(tuples_list) == 2:
            fe = tuples_list[0]
            se = tuples_list[1]
            if fe[1] > se[1]:
                return [ints[se[0]],ints[se[1]]]
            return [ints[fe[0]],ints[fe[1]]]

    if not tuples_list:
        return None
    if len(tuples_list) == 1:
        return [ints[tuples_list[0][0]],ints[tuples_list[0][1]]]

        

7. Optimal solution(Not mine) : This simple solution shines as the no of lines is 1/5th of my implementation and still maintains a cache and gets the entries as well. Elegant and really optimal.

def sum_pairs(list, sum):
  s = set()
  for v in list:
    if (sum - v) in s:
      return [sum - v, v]
    s.add(v)

Lessons learnt

The optimal solution here is implemented in 1/5th of the lines and takes 1/3rd of the running time. So some insights while trying to figure the solution are.

  1. The optimal solution just focuses on getting the numbers which add up to the required target sum. It does not maintain indexes to get the one with the smallest gap. This eliminates all the need to cache, compare and return the correct indexes.
  2. Set is slower than list in append operations. So where ever possible use a list as its append() makes it super fast than set’s add().

| Posted in codewars, CP/CI | No Comments »
10.15.21

Hello world!

Welcome to WordPress. This is your first post. Edit or delete it, then start writing!

| Posted in Uncategorized | Comments Off on Hello world!