Find pairs of integers (a, b) in an array such that a = b + k in linear time - elements are not unique A while ago, I was asked to solve a question similar to this:


  We are given an array arr and we would like to find all pairs of items (a, b) where a = b + k. The items are NOT unique and it is also possible to have k = 0.


I know that if items are unique, this problem can be solved in linear time by using a hashmap. However, when items are NOT unique, I think that the problem becomes very different.

See this example:

arr = [1, 1, 1, 1, 1]
k = 0


The expected output is:

(1, 1), (1, 1), (1, 1), (1, 1) // For the first element
(1, 1), (1, 1), (1, 1)         // For the second element
(1, 1), (1, 1)                 // For the third element
(1, 1)                         // For the fourth element


As it is obvious to me, in the worst case (the above example) the output is of size $n \choose 2$, which is $\Theta (n^2)$. How is it possible to have a linear algorithm, when the output size is definitely $\Theta (n^2)$?

My interviewer insisted that it is possible to still solve it in linear time, if the correct data structure is used.
If you must write out all of the pairs individually, then the overall problem takes quadratic time because the running time of this last post-processing step is $O(n^2)$.

If you are allowed to represent the output in a different way, then you can simply keep track of distinct pairs and associate them with a counter (see run-length encoding). Thus, you can compute the solution in $O(n)$ time using the following algorithm:


Initialize an auxiliary array (or hash map) $Aux$.
Perform a first linear scan of the input array $Arr$ and use the auxiliary array to keep track of how many times each of the elements appears. For example, $Aux[2]=3$ indicates that $2$ appears $3$ times in $Arr$.
Perform a second linear scan of the input array $Arr$. During the $i$th iteration, $a=Arr[i]$ and you must look for the element $b =a-k$, which appears $c =Aux[b]$ times in $Arr$. If $c \gt 0$, then you will add the pair $(a,b)$ to your solution, associated with the count $c$. Two special cases that must be considered at step 3:


If the pair already exists in your solution, you can simply increment the existing counter by $c$.
If $k=0$, you must add the pair $(a,b)$ only if $c \gt 1$. The counter associated with this pair will not be set to (or incremented by) $c$, but, rather, by $c-x-1$, where $x$ stores how many times we have seen $a$ before.