Coding interview Essentials

4. Two numbers sum problem

Two numbers sum problem

Introduction

The problem described in this lesson is probably one of the most asked during coding interviews nowadays, mostly during the early online stages of the hiring process: the interviewer pretty much expects a candidate to be at least familiar with the problem or to have read it at some point during his preparation.

The problem is hard enough to require non-trivial insights in order to be able to write a non-trivial solution but, at the same time, it is not so hard that it would take you hours to come up with something meaningful to say or to write.

We will have a look at a number of solutions: First, we will start from the inefficient brute force approach (and we will later refine it into a fast and time-optimal one); Then we will delve also into a radically different approach based on sorting; finally, we will condense the strengths of all the solutions investigated so far into a time and space optimal solution that we think would do better in an interview context. As we will see, the final solution is efficient and not terribly difficult to write and explain (which are fundamental aspects of every successful coding interview).

Problem statement

Write a function that takes an array of integers \(A\) of size \(n\) and an integer \(T\), and returns true if the sum of any two distinct elements \(I\) is equal to \(T\), false otherwise.

More formally: Given an array \(=\{a_1,...,a_n\}\) and \(T\), where \(a_i, T \in \mathcal{N}\), return:

  • true if \(\: \exists \;i,j \:\: i \neq j\) s.t. \(a_i+a_j = T\)

  • false otherwise


Given \(A=\{9, 4, 17, 42, 36, -3 ,15\}\) and \(T=14\), the function returns true because we can obtain \(14\) by summing up together the elements \(17\) and \(-3\). If \(T=17\) the answer is false.


Given \(A=\{1,3,7\}\) and \(T=8\), the function returns true because we can obtain \(8\) by summing up together the elements \(7\) and \(1\). If \(T=6\) the answer is false.

Clarification Questions

Is the input array modifiable?

Yes, the input array can be modified.

Are the integers guaranteed to be all positive or all negative?

No, \(A\) can contain positive or negative numbers.

Are the values in \(A\) guaranteed to be from a given range?

No, the input is arbitrary. No assumption can be made on the magnitude of the elements of \(A\).

Can a pair be made from an element and itself?

No, the pair’s elements should be distinct. You cannot use the same element \(a_i\) twice. You can however use two elements at indices \(i\) and \(j\) s.t. \(i \neq j\) and \(a_i=a_j\).

Are all elements in the array unique?

No, duplicates are allowed.

Is the input sorted?

No, the ordering of \(A\) is arbitrary.

Shall the function integer overflow be considered when performing the sum of two integers? Is it possible for two elements of \(A\) to sum up to a value that does not fit in a standard ?

No, you do not need to worry about overflow.

Discussion

Brute-force

The brute force solution is fairly straightforward because it consists of a direct application of the formal problem statement. The solution space consists of all possible ordered pairs \((a_i,a_j)\), \(i < j\). Two nested loops can be used to enumerate all those pairs, and, for each of them, we can check whether their sum is equal to \(T\): if that is the case, then true can be immediately returned, otherwise, if we have checked every possible pair and none of them was good, then we can return false. You will find an a fomalization and an implementation of this idea in Algorithm [algo:two_number_sum_bruteforce] and Listing [list:two_number_sum_bruteforce]), respectively.

End Function

Listing 1: C++ solution of the two number sum problem with a brute force approach.

bool two_numers_sum_bruteforce(const std::vector<int> &A, const int T)
{
  const size_t size = A.size();
  for (int i = 0; i < size - 1; i++)
    for (int j = i + 1; j < size; j++)
      if (A[i] + A[j] == T)
        return true;
  return false;
}

The time complexity of this solution is \(O(n^2)\) because there is a quadratic number of ordered pairs and in the worst case, we will look at all of them.

The number of iterations of the internal loop depends on the value of \(i\) and it is described by the function: \(f(i) = n-i-1\). The total number of iteration the second loop runs in the worst case is the the sum of \(f(i)\) for all values of \(i\): \(\sum_{i=0}^{n-2} f(i) = (n-1) + (n-2) + (n-3) \ldots + 1 =\sum_{x=1}^{n-1} x= \frac{n(n-1)}{2} = O(n^2)\)

The space complexity is \(O(1)\).

Hashing

The internal loop of the brute force solution above can be eliminated entirely with the help of a hash table. The key insight is that if a solution exists involving \(a_i\) then, it must the case that exists another element \(a_j = a_i-T\) with \(i > j\).

What this means in practice is that we can loop through \(A\) one element at a time and keep track, in a lookup table, of all the elements seen so far, so that the lookup operation for the aforementioned element \(a_j\) can be performed in constant time.

Algorithm [algo:two_number_sum_hashset] and Listing [list:two_number_sum_hashing] shows this idea in code.

End Function

Listing 2: C++ solution of the two number sum problem using hashing.

bool two_numers_sum_hashset(const std::vector<int> &A, const int T)
{
  std::unordered_set<int> H;
  const size_t size = A.size();
  for (int i = 0; i < size ; i++)
  {
    if (H.find(T-A[i]) != end(H))
      return true;
    H.insert(A[i]);
  }
  return false;
}

The time complexity of this approach is \(O(n)\) (technically is linear on average due to complexity of lookups in hash tables) because the input array is scanned once and for each of its elements, only one lookup and insertion are performed in the hash table (both operations costing constant time on average).

The space complexity is also \(O(n)\), as in the worst case the whole input array is stored in the lookup table.

A common mistake when solving this problem using this approach is to insert the whole input array into the lookup table, and only after searching for \((T-a_i)\). The mistake becomes evident when \(T\) is an even number (\(2 | T\)) and \(\frac{T}{2}\) appears in \(A\) exactly once, at index \(k\) i.e. \(a_k = \frac{T}{2}\) causing to return true, which is wrong because this corresponds to a solution where we sum \(a_k\) twice to obtain \(T\).

For instance, when \(A=\{1,2,5,4\}\) and \(T=10\) this approach wrongly returns true, even if there are not two elements at distinct indices in \(A\) whose sum is \(T\) (we would use \(5\) twice to obtain \(10\)).


  • \(A=\{1,2,5,4\}\)

  • \(T = 10\)

Algorithm [algo:two_numbers_sum_hashset_wrong] wrongly return true even if there are not two distinct elements whose sum is \(10\).

End Function

As with countless other problems on arrays, sorting the input often opens the way to a faster and more efficient solution.

We can start by asking ourselves how the problem changes if \(A\) is sorted. Sorted arrays are naturally associated with binary search, and for good reasons! Many problems can be solved efficiently by pairing sorting and binary search on arrays. This problem is not different, and we can use binary search if \(A\) is sorted to substitute the internal loop of the brute force solution presented [above](). This way, we can lower the overall complexity down to \(O(n log(n))\); it costs \(O(n log(n))\) to sort the input array in the first place, and the actual search consists of \(n\) binary searches, each of them costing \(O(log(n))\).

The space complexity is \(O(1)\) because no additional space is required, since the array is sorted in place.

Listing [list:two_number_sum_sorting] shows a C++ implementation of this idea. Notice that it uses from the C++ standard library and that a possible follow-up question might be to show your own version of the binary search algorithm.

Listing 3: C++ solution of the two number sum problem with sorting and binary search.

bool two_numers_sum_sorting(std::vector<int> &A, const int T)
{
  std::ranges::sort(A);
  const size_t size = A.size();
  for (int i = 0; i < size - 1; i++)
    if (std::binary_search(begin(A) + i + 1, end(A), T-A[i]))
      return true;
  return false;
}

Sorting and two pointers technique

There is a variation to the to the approach described in Section 4.3.3 which still involves sorting but uses a two-pointers technique instead of binary search to finish the job.

The key idea is that once \(A\) is sorted, the algorithm initializes two pointers, one starting at the beginning (\(p_s\)) and the other at the end (\(p_e\)) of the array, respectively. It continues by looking at the sum of the two elements pointed by the two pointers and moving one of the two at each step using the following logic:

  • if \(a[p_s]+a[p_e] = T\) a solution has been found. The algorithm returns true.

  • if \(a[p_s]+a[p_e] > T\), \(p_e=p_e-1\). The right pointer is moved to the left. Moving \(p_e\) to the left has the effect of making the sum of the values pointed by the two pointers smaller (this has an effect at the next iteration).

  • if \(a[p_s]+a[p_e] < T\), \(p_s=p_s+1\). The right end pointer is moved to the left. Moving \(p_s\) to the right has the effect of making the sum of the values pointed by the two pointers larger.

Listing [list:two_number_sum_two_pointers] shows an implementation of the idea above. Notice that compared to the solution using the binary search, this one is shorter and simpler to write. Moreover, it does not use library functions.

Listing 4: C++ solution of the two number sum problem with the two pointers tecnique.

bool two_numers_sum_two_pointers(const std::vector<int> &A, const int T)
{
  int s = 0, e = A.size() - 1;
  while (s < e)
  {
    const int sum = A[s] + A[e];
    if (sum < T)
      s++;
    else if (sum > T)
      e--;
    else
      return true;
  }
  return false;
}

Despite the overall time complexity is still \(O(n log(n))\), this solution is likely to be faster than the one using binary search, mostly due to the fact that the array is scanned linearly (which makes caches happier) by the two pointers and not in a scattered way as in the case of binary search.

Common Variations

Four numbers sum problem

Problem statement

Write a function that takes four arrays of integers, \(A,B,C,D\) and a integer \(T\), and returns how many distinct tuple \((i,j,k,l)\) where exist such that \(A_i+B_j+C_k+D_l = Y\).


Given:

  • \(A=\{1,2\}\),

  • \(B=\{-2,-1\}\),

  • \(C=\{-1,2\}\),

  • \(D=\{0,2\}\), and

  • \(T = 0\)

The answer is \(2\) because the only two valid tuples are:

  1. \((0,0,0,1)\): \(A_0 + B_0 + C_0 + D_1 = 1 + (-2) + (-1) + 2 = T = 0\)

  2. \((1,1,0,0)\): \(A_1 + B_1 + C_0 + D_0 = 2 + (-1) + (-1) + (-1) = T = 0\)

Naïve \(O(n^4)\) solution

We can solve this problem very easily by using the same approach we have described in Section 4.3.1. The idea is that we can use four nested loops and enumerate all possible 4-elements tuples of indices. Listing [list:two_number_sum_naive] shows how such an idea can be implemented. Goes without saying, that this is not the fastest solution we can come up with, considering it has a time complexity of \(O(n^4)\)

Listing 5: Brute force na\ive solution to the four numbers sum problem.

int four_sum_bruteforce(const std::vector<int>& A,
                        const std::vector<int>& B,
                        const std::vector<int>& C,
                        const std::vector<int>& D,
                        const int T)
{
  int ans = 0;
  for (size_t i = 0; i < A.size(); i++)
    for (size_t j = 0; j < B.size(); j++)
      for (size_t k = 0; k < C.size(); k++)
        for (size_t l = 0; l < D.size(); l++)
        {
          const long sum = (long)A[i] + (long)B[j] + 
                           (long)C[k] + (long)D[l];
          if (sum == T)
            ans++;
        }

  return ans;
}

Needless to say, that this is not the fastest solution we can come up with, considering it has a time complexity of \(O(n^4)\).

\(O(n^3)\) solution

The trivial solution shown in Listing [list:two_number_sum_naive] can be improved by using a similar reason that lead us improve the brute-force quadratic time solution for the two numbers problem in Listing [list:two_number_sum_bruteforce] to the linear time (and space) in Listing [list:two_number_sum_hashing].

The idea is that inner-most loop is searching for a value \(D_l = x\) s.t. if it summed to \(A_i+B_j+C_k\) gives us \(T\); in other words: \(x+(A_i+B_j+C_k)=T\). Therefore \(x = T-(A_i+B_j+C_k)\). If there is a way of avoiding a linear search in the array \(D\) for such a value, then we could bring down the complexity from \(O(n^4)\) to \(O(n^3)\).

Thankfully, this is possible if we use a hash map. If we create a hashmap mapping the value of \(D\) and to their frequencies, the inner-most loop of the \(O(n^4)\) solution above can be substituted with a query to the hashmap which runs in constant time (on average).

Listing [list:two_number_sum_cubic] shows an implementation of such idea. Notice that, in order to obtain the maximum saving in terms of work avoided, the arrays are rearranged in such a way so that \(D\) is the longest of the four input arrays.

Listing 6: Brute force cubic time solution to the four numbers sum problem.

int four_sum_cubic(std::vector<int>& A,
                        std::vector<int>& B,
                        std::vector<int>& C,
                        std::vector<int>& D,
                        const int T)
{
    if(A.size() > D.size())
        std::swap(A,D);
    if(B.size() > D.size())
        std::swap(B,D);
    if(C.size() > D.size())
        std::swap(C,D);  

  //D is now the longest
  std::unordered_map<int,int>Dmap; //frequencies map for D
  for(const auto d : D)
      Dmap[d]++;

  int ans = 0;
  for (size_t i = 0; i < A.size(); i++)
    for (size_t j = 0; j < B.size(); j++)
      for (size_t k = 0; k < C.size(); k++){
          const long sum = (long)A[i] + (long)B[j] + 
                           (long)C[k];
          if(auto it = Dmap.find(T-sum) ; it != Dmap.end()){
              ans+=it->second;
          }
      }

  return ans;
}

\(O(n^2)\) solution using hashing

This problem can be however be solved in quadratic time if we use hashmaps in a smarter way, to hold the frequencies of all the values we can obtain by summing up any two elements of \(A\) and \(B\) and of \(C\) and \(D\). The key idea is that we can build two distinct hashmaps:

  • \(AB\): holding the frequencies of the values obtainable by summing any two elements of \(A\) and \(B\)

  • \(CD\): holding the frequencies of the values obtainable by summing any two elements of \(C\) and \(D\).

The space required for both \(AB\) and \(CD\) is quadratic, which is more than the space used by any of the previous solutions, but this extra space enables us to solve this variation also in quadratic time.

The idea is that we are going to spend \(O(n^2)\) time to construct both \(AB\) and \(CD\) and then again \(O(n^2)\) to calculate the final answer by searching into \(CD\) for the value \(T-y\) where \(y\) is an element of \(AB\). If such a value exists in \(CD\) it means that there exists one element in \(A\) and one in \(B\) such that they sum up to \(y\) and one element \(C\) and one in \(D\) such that they sum up to \(T-y\). Summing all these elements up gives: \(y+T-y = T\). This approach is shown in Listing [list:two_number_sum_quadratic].

Listing 7: Quadratic time solution to the four numbers sum problem.

int four_sum_hashing(const std::vector<int>& A,
                    const  std::vector<int>& B,
                     const std::vector<int>& C,
                     const std::vector<int>& D,
                     const int T)
{
  const size_t size = A.size();
  std::unordered_map<int, int> ab;
  for (size_t i = 0; i < size; i++)
    for (size_t j = 0; j < size; j++)
      ab[A[i] + B[j]]++;

  std::unordered_map<int, int> cd;
  for (size_t i = 0; i < size; i++)
    for (size_t j = 0; j < size; j++)
      cd[C[i] + D[j]]++;

  int ans = 0;
  for (const auto [k, v] : ab)

    if (auto it = cd.find(T-k); it != cd.end())
      ans += v * it->second;

  return ans;
}

Notice that the first thing we do is to fill \(AB\) by looping over all possible pairs of elements from \(A\) and \(B\). We then do the same thing for \(CD\), and finally, in the last loop, we take care of calculating the answer by searching, for each element \((k,v)\) of \(AB\), where \(k\) is the sum obtained by one element of \(A\) and one of \(B\), and \(v\) is the number of ways we can obtain it, into \(CD\) for the target value \(T-k\). If such a value exists into \(CD\) then we know we can obtain \(T\). The number of times that is possible is dictated by the frequencies of \(k\) and of the target value in \(CD\).

However, you might have already noticed that we do not really need to explicitly create the map \(CD\). The idea is that when we create \(CD\) we already have all the values of \(AB\) and therefore for a given \(C_i+D_j\) we can already find out how many pairs in \(AB\) exists that we can use to get a total sum of \(T\). This optimization does not really change the overall space complexity but in practice this mean that we use half the memory and we avoid doing \(O(n^2)\) work by eliminating the last loop.

Listing [list:two_number_sum_quadratic_opti] shows this optimized version.

Listing 8: Space optimized quadratic time solution to the four numbers sum problem.

int four_sum_hashing_space_optimized(const std::vector<int>& A,
                                     const std::vector<int>& B,
                                     const std::vector<int>& C,
                                     const std::vector<int>& D,
                                     const int T)
{
  const size_t size = A.size();
  std::unordered_map<int, int> ab;
  for (size_t i = 0; i < size; i++)
    for (size_t j = 0; j < size; j++)
      ab[A[i] + B[j]]++;

  int ans = 0;
  for (size_t i = 0; i < size; i++)
    for (size_t j = 0; j < size; j++)
      if (auto it = ab.find(T-(C[i] + D[j])); it != ab.end())
        ans += it->second;

  return ans;
}