Interview question - Given an array find four elements such that A + B = C + D

Problem Statement:

Given an array A of integers, find the index of values that satisfy A + B = C + D, where A,B,C & D are integers values in the array.

Note:

1) Return the indices `A1 B1 C1 D1`, so that A[A1] + A[B1] = A[C1] + A[D1] A1 < B1, C1 < D1 A1 < C1, B1 != D1, B1 != C1 2) If there are more than one solutions, then return the tuple of values which are lexicographical smallest. Assume we have two solutions S1 : A1 B1 C1 D1 ( these are values of indices int the array ) S2 : A2 B2 C2 D2 S1 is lexicographically smaller than S2 iff A1 < A2 OR A1 = A2 AND B1 < B2 OR A1 = A2 AND B1 = B2 AND C1 < C2 OR A1 = A2 AND B1 = B2 AND C1 = C2 AND D1 < D2

Example:

Input: [3, 4, 7, 1, 2, 9, 8]
Output: [0, 2, 3, 5] (O index)


If no solution is possible, return an empty list.

Solution Approach:

Brute force approach will be to simply iterate over the array 4 times to generate all possible combinations and then verify where we get a tuple satisfying all the condition listed above or not. It looks like:
 
for (int i = 0; i < len; i++) {
     for (int j =0 ; j < len; j++) {
          for (int k = 0; k < len; k++ )  {
               for (int l = 0; l < len; l++)  {
                     // Check if A[i]+A[j] == A[k] + A[l]
                     // and it satisfies other conditions listed above.
               }
          }
     }
}
The brute approach as it looks isn't efficient and thus we need to look for something better. To trade off time complexity we need to look into solutions that requires extra memory. Also, let us change the problem statement a bit. Instead of generating a quadruple, let us generate pairs of 2 integer elements from the array.

For example:

Input: [3, 4, 7, 1, 2, 9, 8]
Array containing all pairs : [7, 10, 4, 5, 12, 11, 11, 5, 6, 13, 12, 8, 9, 16, 15, 3, 10, 9, 11, 10, 17]

If you look closely at the resultant array containing sum of all possible pairs by taking 2 elements at a time from the input array, the problem now becomes much simpler. We need to find a pair of 2 elements whose values are equal. The only trick here will be maintain the conditions mentioned in the problem statement, since we have many such pairs and we need to return only one out of them.

The extra memory required here will be O(n2) . Following is a complete java solution based on this approach where I have used a HashMap to maintain the resultant pairs and evaluate the conditions listed in the original array.

public class Solution {
    public ArrayList<Integer> equal(ArrayList<Integer> a) {
        ArrayList<Integer> res = null;
        HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
        
        for (int i = 0; i < a.size(); i++) {
            for (int j = i+1; j < a.size(); j++) {
                int sum = a.get(i) + a.get(j);
                
                if (map.containsKey(sum)) {
                    ArrayList<Integer> pair = map.get(sum);
                    if (pair.get(0) != i &&
                        pair.get(1) != j &&
                        pair.get(0) != j &&
                        pair.get(1) != i) {
                            ArrayList<Integer> _temp = new ArrayList<>();
                            _temp.add(pair.get(0));
                            _temp.add(pair.get(1));
                            _temp.add(i);
                            _temp.add(j);
                            
                            if (res == null) res = _temp;
                            else {
                                for (int k = 0; k < 4; k++) {
                                    if (res.get(k) < _temp.get(k)){
                                        break;
                                    } else if (res.get(k) > _temp.get(k)) {
                                        res = _temp;
                                        break;
                                    }
                                }
                            }
                            
                        }
                } else {
                    ArrayList<Integer> pair = new ArrayList<>();
                    pair.add(i);
                    pair.add(j);
                    map.put(sum, pair);
                }
            }
        }
        
        return res;
    }
}
- Happy Programming !!

comments powered by Disqus