Python Beginner Algorithms Tutorial

Two Sum II (via Leetcode)

Problem found on Leetcode.

Problem statement:

Given a list of integers that is sorted in ascending order, find two numbers in the list that add up to a specific target number.

The function should return the indices of the tow numbers such that they add up to the target. The first index returned should be smaller than the next one. For this problem, assume index starts at 1, not traditional zero-based indexing.

Assume a solution exists.

Test Cases

In [ ]:
# assert two_sum(numbers=[0, 3, 5, 9], target=8) == [2, 3]

The sum of 3 and 5 is the target value of 8. Since this is one-based indexing, 3 and 5 are respectively at indices 2 and 3.

In [ ]:
# assert two_sum(numbers=[9, 10, 5, 15], target=25) == [2, 4]
In [ ]:
# assert two_sum(numbers=[-3, -1, 0, 3], target=-4) == [1, 2]

Solution #1 - the Brute Force Way

Pseudocode

In [ ]:
# create function that takes in list of numbers and target
    # for each index and num in numbers:
        # for every *other* index2 and num2 in numbers:
            # if num and num2 add up to target
                # return two indices as list

Code

In [36]:
def two_sum(numbers, target):
    # outer loop ensures we don't reach last num in numbers b/c nothing to compare it to
    # index starts at base zero
    for index, num in enumerate(numbers[:-1]):
        # below loop ensures we don't compare num to itself and only examine following nums
        # index2 starts at num that's index+1 value in each iteration...
        for index2, num2 in enumerate(numbers[index+1:]):
            if num + num2 == target:
                # add 1 to each index value b/c of one-based indexing
                # 2nd list item started at index+1 and could iterate to index2 indices further; add 1 at end too
                return [index+1, index+1+index2+1]

Complexity

I would generally not recommend solving the problem this way in a coding interview or using a similar solution in production. I demonstrated it this way simply to show a solution with minimal code and logic needed to arrive at the correct result.

Let n be the count of values in numbers.

Time complexity at worst case is O(n^2) because for each element in numbers, I compare it to nearly every other number in numbers.

Space complexity is nothing.

Run Test Cases

In [37]:
assert two_sum(numbers=[9, 10, 5, 15], target=20) == [3, 4]
In [38]:
assert two_sum(numbers=[-3, -1, 0, 3], target=-4) == [1, 2]

Solution #2 - a More Performant Way

Pseudocode

In [ ]:
# create a function that takes in a list of numbers and a target

    # we want to keep track of numbers iterated over in a set to allow for easy O(1) lookups...
    
    # create an empty set to hold nums iterated over
    # iterate over index and num in numbers:
        # if target-num is in set:
            # break out of loop
        # else:
            # add num to set
            
    # lookup index of this greater value in list...
    # for index2 and num2 in numbers:
        # if num2 == target-num and index is not equal to index2:
            # this is the value we want to find to add up to sum
            # return [index, index2]

Code

In [42]:
def two_sum(numbers, target):
    nums_covered = set()
    for index, num in enumerate(numbers):
        if target-num in nums_covered:
            break
        else:
            nums_covered.add(num)
    
    for index2, num2 in enumerate(numbers):
        if num2 == target-num and index != index2:
            return [index2+1, index+1]

Alternatively, this code could be written without a second iteration over numbers. Instead, I could use a dictionary to store all the index positions for each num in numbers. So when I find a number in iteration and in the set that add to sum, look up the number found from the set in the dictionary as an O(1) time lookup to find its corresponding index.

Complexity

Time complexity is at worst cast O(2n) because there can be nearly two complete iterations over numbers.

Space complexity is O(n) because the set created, nums_covered could at worst case hold nearly all values in numbers.

Run Test Cases

In [43]:
assert two_sum(numbers=[9, 10, 5, 15], target=20) == [3, 4]
In [44]:
assert two_sum(numbers=[-3, -1, 0, 3], target=-4) == [1, 2]