Coding Problem: Two Sum

This article was originally posted on my website.

DailyCodingProblem is a great website that sends coding problems to your inbox daily.

The Question

Given a list of numbers and a number k, return whether any two numbers from the list add up to k.

Examples

1. [1, 2, 3], k = 4

Yes, since 1+3 = 4

1. [10, 15, 3, 7], k=17

Yes, since 10+7 = 17

1. [5, 4, 7, 12, 1], k = 2

No

Solutions

Brute force

A simple solution would be to iterate over all possible pairs in the array and checking if a pair adds up to k.

for i from 0 to n-1:
  for j from i+1 to n-1:
    if a[i] + a[j] == k:
      return true
return false

This will involve n(n+1)/2 steps, so the time complexity will be O(n^2), and O(1) space complexity.

Sorting and two-pointer approach

We can sort the array and use two pointers, front (starting from 0) and end (starting from n-1):

1. If the elements pointed to currently sum up to k, then return true
2. If the sum is less than k, increment the front pointer, since we need to increase the sum and the array is sorted.
3. Symmetrically, if the sum is more than k, decrement the end pointer. We repeat this until front and end cross each other.

sort(a)
front = 0, end = n-1
while front < end:
  if a[front] + a[end] == k:
    return true
  else if a[front] + a[end] < k:
    front = front + 1
  else
    end = end - 1
return false

Since we are sorting an array (O(nlogn)) and looping with the front and end pointers (O(n)), the overall time complexity of this solution is (O(nlogn)). The space complexity is (O(1)).

You can find the implementation of this solution here

If we are required to return the indices, the sorting approach cannot be used directly. We will have to make an array of pairs of (val, index) and then sort this array.

Using a set or map

We can iterate through the array and keep adding the elements to a set (or hashset, map or hashmap), and for every element, check if the set contains (k-a[i]). If we find this condition to be true, then there exists a pair that adds up to k: the current a[i] and the entry in the set, k-a[i].

set m
for i from 0 to n-1:
  if m.has(k-a[i]):
    return true
  m.add(a[i])
return false

We are making a single pass through the array, finding whether a number exists in the set, and adding an element to the set. If we are using a BST implementation of set (C++ set or map) then the time complexity will be O(nlogn), since every insert/find operation takes O(logn) time. If we use a hashset or hashmap (C++ unordered_set or unordered_map) then the time complexity will be O(n), since insert/find operation can be done in constant time.

You can find the implementation of this solution here

If we are required to return indices of these elements, then need to use a map or hashmap, with the key-value pairs as (value, index).