Find four elements that sum to a given value [reviewed]

Problem

You're given an array of integers(eg [3,4,7,1,2,9,8]) Find the index of values that satisfy A+B = C + D, where A,B,C and D are integers values in the array. 

Eg: Given [3,4,7,1,2,9,8] array

3+7 = 1+ 9  satisfies A+B=C+D

so print (0,2,3,5)

1. Two sum problem

First all all, we can break this problem into simpler problem. Finding the two numbers that sum to a given number is typical "two sum" problem. Using the hashtable, which takes $O(1)$ for search operation, we can solve this problem in $O(N)$.

Here is the complete code running in $O( N^2 )$, base on the assumption that the Hashtable provides $O(1)$ time for search. However, I used std::map, which provides $O(\log{N}$) for search, so the overall running time is $O(N^2 \log {N})$

 Give the S, the sum as an input, algorithm is as below:

1. put integers in the array into Hashtable, $H$. ( $O(N)$ )
2. Iterate over the integers in the array, for each integer, x in the array, check if $S-x$ exists in the hashtable, H.  (running time $ O (N) * O(1) = O(N)$)
   

2. Extending to the bigger problem

Now, we know how to find the two numbers in $O(N)$ time, given the array, $N$. How can we apply this idea to 4 integers satisfying the following? $$A+B = C+D, where A \in N, B \in N, C \in N,D \in N$$

What if we can convert above equation into the following? $$A+C = S,  where S = C+D, C\in N, D \in N$$

If we can do that, this problem become the two sum problem again.
We can preprocess the integers in array $N$, produce the list of sum of two unique integers. This process will take $O(N^2)$ time.

Let's call this list, $S_{c,d}$.

All we need to do is to find two integers other than $C, D$ making up $S \in S_{c,d}$ using two sum algorithm. Let calculate the overall running time.

   1) iterating over $S_{c,d}$ takes $O(N)$.
   2) For each $S \in S_{c,d}$, running a two sum algorithm takes $O(N)$

This will take $O (N^2)$ time.

The implementation blow used the std::map instead of HashTable. This gives $O( \log {N})$ search instead of $O(N)$, thereby resulting in $O(N^2 \log {N})$ running time.




Practice statistics

25:52: to write up the code in a paper
5:18 : to verify the code (made minor typo)


UPDATE(2019-07-26): solved the problem again. Came up with the right algorithm but code had a bug of adding the solution twice.

Here is a solution in python


Practice statistics:

7:00: come up with algorithm
15:00: write up the code
5:00: debugging and fix the errors.
6:00: had to fix the problem of recursion.