CODEWITHSUNDEEP
pythonpython-3.xalgorithm
jaiyeko
jaiyeko

Reputation: 151

Find pairs of numbers that add to a certain value?

I have a function match that takes in a list of numbers and a target number and I want to write a function that finds within the array two numbers that add to that target.

Here is my approach:


>>> def match(values, target=3):
...     for i in values:
...             for j in values:
...                     if j != i:
...                             if i + j == target:
...                                     return print(f'{i} and {j}')
...                             return print('no matching pair')

Is this solution valiant? Can it be improved?

Upvotes: 0

Views: 915

Answers (2)

awakenedhaki
awakenedhaki

Reputation: 301

There is room for improvement. Right now, you have a nested loop. Also, you do not return when you use print.

As you iterate over values, you are getting the following:

values = [1, 2, 3]
target = 3

first_value = 1
difference: 3 - 1 = 2

We can see that in order for 1 to add up to 3, a 2 is required. Rather than iterating over the values, we can simply ask 2 in values.

def match(values, target):
    values = set(values)
    for value in values:
        summand = target - value
        if summand in values:
           break
    else:
        print('No matching pair')
    print(f'{value} and {summand}')

Edit: Converted values to a set since it has handles in quicker than if it were looking it up in a list. If you require the indices of these pairs, such as in the LeetCode problem you should not convert it to a set, since you will lose the order. You should also use enumerate in the for-loop to get the indices.

Edit: summand == value edge case

def match(values, target):
    for i, value in enumerate(values):
        summand = target - value
        if summand in values[i + 1:]:
           break
    else:
        print('No matching pair')
        return
    print(f'{value} and {summand}')

Upvotes: 0

lenik
lenik

Reputation: 23556

The best approach would result in O(NlogN) solution.

  1. You sort the list, this will cost you O(NlogN)
  2. Once the list is sorted you get two indices, the former points to the first element, the latter -- to the latest element and you check to see if the sum of the elements matches whatever is your target. If the sum is above the target, you move the upper index down, if the sum is below the target -- you move the lower index up. Finish when the upper index is equal to the lower index. This operation is linear and can be done in O(N) time.

All in all, you have O(NlogN) for the sorting and O(N) for the indexing, bringing the complexity of the whole solution to O(NlogN).

Upvotes: 1

Related Questions