Python pair sum problem in O(n) clarification

Question

Given an integer array, output all of the unique pairs that sum up to a specific value k.

Here is the standard solution, in O(n) time:


    if len(arr) < 2:
        return 

    seen = set()
    output = set()

    for num in arr: 

        target = k - num

        if target not in seen: 
            seen.add(num)

        else:
            output.add((min(num, target), max(num, target))) 


    return print('\n'.join(map(str, list(output))))

I have a few questions regarding this solution:

1) Why do we use a set to store the seen values of the array? Why not a list? Does this change anything?

2) Why the min(num, target), max(num, target)? Is this for the sake of consistent formatting or is there a deeper reason behind this? At first, I thought it would be to deal with duplicate cases such as (1,3) & (3,1), but this solution doesn't come across that I don't think?

See https://stackoverflow.com/a/2831242/1862861 regarding why you would use a set rather than a list. They're more efficient when checking if they already contain a value. — Matt Pitkin, May 08 '20 at 21:12

score 1 · Answer 1 · answered May 08 '20 at 23:09

1) Set is a faster way in python to check if a value exists in and not to store duplicates that not needed in this case.
2) The reason of doing (min(num, target), max(num, target)) is probably to add to the output set a tuple that contains both of the numbers in the order of (min, max) that it will print in the last print statement in a better format.

Python pair sum problem in O(n) clarification

1 Answers1