Pairs with Sum

16.24 Pairs with Sum: Design an algorithm to find all pairs of integers within an array which sum to a specified value.

• Brute force: Check every possible combinational pair and see if it matches the sum. O(n^2)

• Better:

  • If we sort the pairs (O(nlogn)), then we can try to map each pair with every other possible pair like before, except this time we can break out of the for loop when we know that the next iteration will exceed the number we expect. We also know when to break out of the loop entirely (when we exceed the value in the outer for loop). Along in the process, we can check for duplicates - and move onto the next iteration. And finally, we can also break out when we get a successful match. This is because we know that there is only a single unique solution per some value in the array A. After a successful match, every after is guarenteed either to not happen, or result in a duplicate pair.

vector<pair<int, int>> pairs_with_sum(vector<int> &nums, int sum) {
    vector<pair<int, int>> pairs;
    if (nums.size() < 1) {
        pairs.push_back(make_pair(INT_MAX, INT_MAX));
        return pairs;
    }

    sort(nums.begin(), nums.end());    

    // algorithm
    for (int i = 0; i < nums.size() - 1; i++) {
        for (int j = i+1; j < nums.size() - 1; j++) {
            int num1 = nums.at(i);
            int num2 = nums.at(j);
            if (num1 == num2) break;
            if (num1 + num2 == sum) {
                pairs.push_back(make_pair(num1, num2));
                break;
            }
            else if (num1 + num2 > sum) break;
            else if (num1 > sum) return pairs;
        }
    }
    return pairs;
}

int main()
{
    // 1,1,2,2,3,3,4,5,6,10
    vector<int> nums = {1,2,3,4,1,2,10,3,5,6};
    vector<pair<int, int>> pairs = pairs_with_sum(nums, 5);
    for (auto i : pairs) {
        cout << i.first << " " << i.second << endl;
    }
    cout << endl;


}

• Even Better:

  • Use a hash table to check for the value you expect for the sum. O(N) time complexity, O(N) extra space.

  • Current flaws: outputs pairs that are essentially redundent. e.g. (2,3) will also output (3,2) its inverse. Depending on the specificity of the problem, I may have to change this. A solution to this may be to use a map, instead of an unordered map, and tell it to look for values beyond a particular interval.

vector<pair<int, int>> pairs_with_sum(vector<int> &nums, int sum) {
    vector<pair<int, int>> pairs;
    if (nums.size() < 1) {
        pairs.push_back(make_pair(INT_MAX, INT_MAX));
        return pairs;
    }

    // if we map the value with its frequency, it allows
    // us to avoid duplicate pairs, and only output unique pairs
    // this also enables us the option of outputting all 
    // possible pairs even if they are duplicates
    unordered_map<int, int> hashB;
    for (auto &i : nums) {
        auto find = hashB.find(i);
        if (find == hashB.end()) {
            // not found
            hashB.insert({ i, 1 });
        }
        else 
            find->second++;
    }

    for (int i = 0; i < nums.size(); i++) {
        int expect = sum - nums.at(i);
        auto found = hashB.find(expect);

        if (found != hashB.end()) {
            // found
            if (found->first != nums.at(i)) {
                pairs.push_back(make_pair(nums.at(i), found->first));
            }
            else if (found->first == nums.at(i)) {
                // we also have to make their that the value detected
                // is not a duplicated element of itself
                if (found->second > 1) {
                    pairs.push_back(make_pair(nums.at(i), found->first));
                }
            }
        }
    }
    return pairs;
}