Problem: Given an unsorted array, find all pairs whose sum is a given number K

Solution 1: Use a hash-map to store all numbers.
When storing a number in the map, lookup N-k.
If N-k exists in the map, sum is found, else move to next number.

Solution 2: Sort the array and search with two indexes set to start and end of the array.

int start = 0;
int end = arr.length;
while (start <= end)
{
int sum = arr[start] + arr[end];
if (sum == K)
{
System.out.println ("Found sum for " + arr[start] + " and " + arr[end]);
start++;
end--;
}
else if (sum < K)
{
start++;
}
else
{
end--;
}
}

Find all triplets with a given sum

A corollary of the above question is to find all triplets with a given sum.

Since the best case for finding pairs was O(n log n) for sorting and then O(n) for finding pairs, it
follows that the order for triplets would be greater than or equal to that.

Taking liberty due to this, let us first sort the array.

Now for each number in the sorted array, we can find a pair whose sum is S-arr[k]

Since finding pairs for a given sum is O(n) in sorted array, the whole operation becomes O(n log n ) + O(n^{2})

Which is equal to O(n^{2})

Now find all quadruples with a given sum

Find sum of all pairs using two loops - O(n^{2}) to get k (i.e. n(n-1)/2) numbers

Sort these k numbers - O (k log k) = O(n^{2} log n^{2}) = O(n^{2} log n)

Find pairs in these sorted 'k' numbers whose sum is the given sum and which do not have any common element from the original array.

Got a thought to share or found a bug in the code? We'd love to hear from you: