Solutions To Challenge I

In case you have not seen or tried to solve the challenge, click here. If you have, well, below is a quick recap of the challenge.

The Problem

You are given an array of numbers–integers–and a separate integer called sum. You must write a function that identifies if any two integers (different indices) in the array add up to sum. The array is not guaranteed to be sorted. The function must return an array with the indices of the two elements that add up to sum, and in the event that no two elements add up to sum, then return an empty array.

Most Efficient Solution

This solution is proposed by me: The asymptotic runtime is O(n), and the space is also O(n). The solution is proposed in C++ (tested with the C++11, C++14, and C++17 compilers)

#include <iostream>
#include <vector>
#include <unordered_map>
#include <limits.h>


using namespace std;


vector<int> findTwoElementsForSum(const vector<int> &v, int sum)
{
    vector<int> result;
    
    // <complement (sum - x), index>
    unordered_map<int, int> visited;
    
    for (size_t i = 0; i < v.size(); i++)
    {
        if (visited.find(v[i]) != visited.end())
        {
            // Sum found!
            result.push_back(visited[v[i]]); // Get index of element
            result.push_back(i);
            return result;
        }
        else
            visited[sum - v[i]] = i; // Not found, add to hash table
        
    }
    
    return result; // this will be empty
}


void test(const vector<int> v, int sum, const vector<int> expectedResult)
{
    vector<int> result = findTwoElementsForSum(v, sum);
    
    if (expectedResult == result)
        cout << "Passed" << endl;
    else
    {
        cout << "Failed:" << endl;
        cout << "Expected: ";
        for (auto& x : expectedResult)
            cout << x << " ";
            
        cout << endl;
        cout << "But obtained: ";
        for (auto& x : result)
            cout << x << " ";
            
        cout << endl;
    }
}


int main()
{
    // Normal test cases
    test({5, 3, 1, 6}, 11, {0, 3});
    test({4, 0, 5, 8}, 9, {0, 2});
    test({5, 3, 1, 7}, 10, {1, 3});

    test({4, -3, 1, 7, -4}, -2, {1, 2});
    test({-4, -3, -1, -7, 4}, 0, {0, 4});
    
    test({6, -530, 4723, 7, 10292}, 500, {});
    test({0, 1, 2, 3, 4}, 10, {});
    test({10000, 20000, 30000, 40000, 50000}, 100000, {});
    
    // Edge and Corner cases
    test({}, 12, {}); // Should return empty result
    test({12}, 12, {}); // Should return empty result
    test({12, 12}, 12, {}); // Should return empty result
    test({INT_MAX, INT_MAX}, INT_MAX, {}); // Should return empty result (overflow)
    test({12, 12, 12, 12, 12, 12}, 12, {});
    test({4, 3, 4, 3}, 7, {0, 1}); // Should find first sum
    test({-1, 4, -4, 5, -4}, 4, {0, 3}); // Should find first sum


    return 0;
}

Analysis

This solution takes advantage of Hash Tables to produce a fast algorithm. In this solution, I used two operations of the hash table data structure: Search and Insert, and as you may know, they are both O(1) on average. The hash table contains the complement of the element–that is, sum - x–which will result in the number needed to add to x for it to be sum as the key, and the index of that element as the value. The idea is that if that needed number is found, then you simply create an array with the index of x (that was in the hash table), and the index of the current element.

If the array is completely traversed and there is no solution, then the hash table will contain n elements, where n is the size of the array, hence our space complexity being O(n).

As far as I know, this is the fastest solution to this problem. Feel free to suggest optimizations.

Your Solutions

You may submit your solutions to this problem to solutions@bryanmorfe.com and if they are efficient, they may be posted here. You may also post optimizations, corrections, and solutions in a comment down below.