# (FB phone interview) find all equivalent pairs

• 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. Find all combinations of quadruples.

similar to leetcode 4sum, or has better solution ?

• Recursive to get all the sum value then compare, shouldnt be hard. but might not be the best eg. [1,2,3,4]

1 + 2 = 3,
1 + 3 = 4,
1 + 4 = 5,

having a map
3 => [{1, 2}]
4 => [{1, 3}]
5 => [{1, 4}]

=======================

2 + 3 = 5
2 + 4 = 6

3 => [{1, 2}]
4 => [{1, 3}]
5 => [{1, 4}, {2,3}]
6 => [{2, 4}]

=====================
3 + 4 = 7

3 => [{1, 2}]
4 => [{1, 3}]
5 => [{1, 4}, {2,3}]
6 => [{2, 4}]
7 => [{3, 4}]

[{1, 4}, {2, 3}]

• This post is deleted!

• 2 nested loops and add sum of each 2 elements in a map, then loop through the map and get lists that has size > 1

Runs in O(n^2) where n is the size of the array
worst space is O(n) where no any pairs sum equal to other pairs

``````class Pair {
int x;
int y;

public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}

void printEquivalentPairsOf4(int[] arr) {
List<List<Integer>> r = equivalentPairsOf4(arr);
for (List<Integer> il : r) {
System.out.println(il.get(0) + ", " + il.get(1));
}
}

List<List<Integer>> equivalentPairsOf4(int[] arr) {
HashMap<Integer, List<Pair>> map = new HashMap<>();
for (int i = 0; i < arr.length - 1; i++) {
for (int j = i + 1; j < arr.length; j++) {
int sum = arr[i] + arr[j];
if (!map.containsKey(sum))
map.put(sum, new ArrayList<Pair>());
}
}

List<List<Integer>> result = new ArrayList<>();
for (List<Pair> v : map.values()) {
if (v.size() > 1) {
for (Pair p : v) {
}
}
}
return result;
}
``````

• @k' worst space is O(n^2)

• @k' worst space is O(n^2)

I think worst case is O(n^4). There are O(n^4) quadruplets of indexes, worst case they all equal to each other.

• @k' if there are more than two pairs in the map for a particular sum , result will have more than 4 entries instead of having more quadruples. How do you solve this ?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.