Two Sum

(link)

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]

Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]

Notice that the problem guarantees exactly one pair that adds to target, and that we cannot add an element to itself.
nums is potentially not in order.

Solutions

Nested Loops

"Simple to implement, inefficient performance, constant space"

Let's look at the example nums = [11, 7, 15, 2], target = 9.

We can try every pair's sum to find the pair that adds up to 9. From here on, we will refer to the first index of the pair first, and the other index as second.

Let's pick 11 as our first number (first = 0, because 11 is the 0th indexed element). This means we will have to pair 11 up with the other numbers, either 7, 15, or 2 to reach target. None of these pairs add up to target. 11 + 7 is not 9, 11 + 15 is not 9, 11 + 2 is not 9.

We pick the second number 7 (first = 1). We can try to pair it with the other numbers (15, and 2) to see if there is a combination that adds to target. 7 + 15 is not 9. 7 + 2 is 9, so we return the indexes first (1) and second (3) and end the function.

# O(n^2) time, O(1) space
def two_sum(nums, target):
    for first in range(len(nums) - 1):
        for second in range(first + 1, len(nums)):
            if nums[first] + nums[second] == target:
                return [first, second]
    return [-1, -1]

We generate every possible pair in nums, which will take O(n^2) time. We are also not creating a new collection so we are not taking up extra space.

Time: O(n^2)
Space: O(1)

Sorting

"We can't afford exponential time, but we still need constant space"

In "two sum"-like problems, it's also important to clarify if there is a space constraint. This is important in real life as well! Speed isn't everything.

We can improve the previous solution's time complexity, without affecting space.

In python, list.sort() is in place and uses O(1) space, but sorted(list) generates a new list and uses O(n) space.
Some languages might only have O(n) space sort. This is good to share to the interviewer. The interviewer might say "let's pretend for now this sorting function is O(1).

# O(nlog(n)) time, O(1) space
def two_sum(nums, target):
    pairs = [(num, i) for i, num in enumerate(nums)]

    # Sort based on values
    pairs.sort()

    # Two-pointer approach
    left, right = 0, len(nums) - 1
    while left < right:
        sum_ = pairs[left][0] + pairs[right][0]
        if sum_ == target:
            # Return original indices
            return [pairs[left][1], pairs[right][1]]
        elif sum_ < target:
            left += 1
        else:
            right -= 1
    return None  # No solution found

Caching

"We really just care about time complexity"

We can take "as much space as we need".

We can cache each of nums' element's complement (target - nums[i]). If one of nums' elements, later in the nums loop, is equal to a complement that we generated earlier, then we have found a pair that adds to target.

# O(n) time, O(n) space
def two_sum(nums, target):
    cache = {}

    for i, num in enumerate(nums):
        comp = target - num
        if comp in cache:
            return [i, cache[comp]]
        cache[num] = i
    return [-1, -1]

Closing thoughts on Two Sum

The "optimal" O(n) time solution is oftenly the memorized solution for Two Sum. However as engineers, we must know when and how to apply each approach in Leetcode or in real life problems.

In Two-Sum type problems, there are three tricks we must have down cold:

1) Brute force, O(n^2) nested loop and O(1) space

2) Efficient space, O(nlog(n)) sorted array and O(1) space

3) Efficient time, but uses a O(n) cache

Two Sum, a deep dive