Find four elements that sum to a given value (Hashmap)

Difficulty Level Hard
Frequently asked in Amazon Google Microsoft
Array Hash SortingViews 2675

The problem “Find four elements that sum to a given value (Hashmap)” states that suppose, you have an integer array and a number called sum. The problem statement asks to determine if four elements present in the array which sums up to the given value “sum”. If true, then function outputs “Yes”, else outputs “No”.

Example

Find four elements that sum to a given value (Hashmap)

arr[] = {2, 7, 3, 2, 9, 5, 9, 3}
sum=25
Yes
arr[] = {4, 3, 1, 6, 8, 5, 4, 1}
sum=30
No

Algorithm

  1. Traverse the loop, while i < n – 1.
    1. Traverse the loop, while j=i+1 < n
      1. Store the value of arr[i] + arr[j] to val and check if sum-val exists in the hash table.
        1. If true, then get the key and find out the number, and return true.
      2. Else, put that i and j in the hash table along with the key as arr[i] + arr[j].
  2. Return false.

Explanation

We are given a problem statement that asks to determine if there are four elements that exist in the array which sums up the given value. If yes, then follow then the function should print yes, else print no. We are going to use hashing to solve this problem. Because of that, we can store the key as our element which pair up to be the possible sub-array, and value as our indexes of that so that we can check on it.

Let us consider an example:

Example

arr[]={ 2, 7, 3, 2, 9, 5, 9, 3 }, sum=25

Here we have taken an example. We have declared a Boolean function which is going to return true and false. We are also going to use object property of which objects we are going to use, in our map, as one of our arguments is any list or vector. So basically we are going to traverse the arrays, but taking each element of an array at one time in an outer loop and traversing rest of the elements that come one index ahead, with the second inner loop.

We take the sum of both of the elements that is arr[i] + arr[j] and store it to some variable called val and then check if sum-val is present in the hashtable or not, if not present then simply push the elements into the map, suppose we have array’s element 2 and 7 (arr[i] and arr[j]) getting sum is 9 and sum-val that is 25-9 is 18 is not present in the hash table, so we simple push 9 and current indexes that is 0 and 1, so that later we can find out if sum-arr[i]+arr[j] is present or not in the table. If present, then simply get the key’s values and check some conditions on it, if it satisfied then return true. It means we found our answer.

C++ code to Find four elements that sum to a given value (Hashmap)

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

typedef pair<int, int> Pair;

bool getFourNumber(int arr[], int n, int sum)
{
    unordered_map<int, vector<Pair>> map;
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            int val = sum - (arr[i] + arr[j]);
            if (map.find(val) != map.end())
            {
                for (auto pair : map.find(val)->second)
                {
                    int x = pair.first;
                    int y = pair.second;
                    if ((x != i && x != j) && (y != i && y != j))
                    {
                        return true;
                    }
                }
            }
            map[arr[i] + arr[j]].push_back({i, j});
        }
    }
    return false;
}
int main()
{
    int arr[] = { 2, 7, 3, 2, 9, 5, 9, 3 };
    int sum = 25;
    int n = sizeof(arr) / sizeof(arr[0]);
    if(getFourNumber(arr, n, sum))
        cout << "Yes";
    else
        cout<<"No";
    return 0;
}

Yes

Java code to Find four elements that sum to a given value (Hashmap)

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Pair
{
    public int x, y;
    Pair(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
}
class printQuadruplets
{
    public static boolean getFourNumber(int[] arr, int n, int sum)
    {
        Map<Integer, List<Pair>> map = new HashMap<>();
        for (int i = 0; i < n - 1; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                int val= (arr[i] + arr[j]);
                if (map.containsKey(sum-val))
                {
                    for (Pair pair : map.get(sum-val))
                    {
                        int x = pair.x;
                        int y = pair.y;
                        if ((x != i && x != j) && (y != i && y != j))
                        {
                            return true;
                        }
                    }
                }
                map.putIfAbsent(arr[i] + arr[j], new ArrayList<>());
                map.get(arr[i] + arr[j]).add(new Pair(i, j));
            }
        }
        return false;
    }
    public static void main(String[] args)
    {
        int arr[] = { 2, 7, 3, 2, 9, 5, 9, 3 };
        int sum = 25;
        if (getFourNumber(arr, arr.length, sum))
        {
            System.out.println("Yes");
        }
        else
            System.out.println("No");
    }
}

Yes

Complexity Analysis

Time Complexity

O(n2) where “n” is the number of elements in the array. Using HashMap allowed us to achieve this time complexity else it would have not been possible.

Space Complexity

O(n2) where “n” is the number of elements in the array. In the worst case there may be N^2 pairs that need to be stored in the map. Thus the space complexity is polynomial.

Translate »