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:

1. Initialize an auxiliary array (or hash map) $Aux$.

2. 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=3$ indicates that $2$ appears $3$ times in $Arr$.

3. 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.

• Let's give your solution a try for the given example [1, 1, 1, 1, 1]. In our Aux array, we have only Aux = 5. At step 3, we are looking for b = 1 - 0; therefore, c = Aux[b] is 5. We add 5 (1, 1) to our solution. At this point, it becomes clear that (for the next steps) to make sure we are not inserting repeated pairs, we have to check the indices. Therefore, the count idea does not apply here. You should know that elements are different, although they all have value 1. – Matin Kh Mar 17 '17 at 16:15
• Mmm, I think you misunderstood the second bulleted point (I am going to edit it, for clarification). If $k=0$, at step 3, iteration 0, you will add $(1,1)$ to your solution. The counter will be $c=5-0-1=4$, which is correct. At iteration 1, you will not add $(1,1)$, but rather increment its counter by $c=5-1-1=3$, which is also correct. At iteration 2, you will increment the counter by $c=5-2-1=2$, and so on ... for a final result of $(1,1)$ and counter equal to $10$. – Mario Cervera Mar 17 '17 at 16:36
• In any case, you are printing (1, 1) 4 times the first time; 3 times the second time; 2 times the third time; and once for the last iteration. Thus, it is still $n \choose 2$. Please note that I was required to return the pairs, so I had to print them. If the question were how many pairs are there? and we did not have to print them... Then yes; your solution would give us that answer in linear time. – Matin Kh Mar 17 '17 at 20:43
• Well, if writing out all of the pairs individually is a requirement, then, IMHO, the overall problem does not take linear time (in contrast to the interviewer's suggestion): the solution can be computed in $O(n)$ time, but there is a post-processing step that takes $O(n^2)$ time. – Mario Cervera Mar 17 '17 at 23:30