A while ago, I was asked to solve a question similar to this:
We are given an array
arrand we would like to find all pairs of items
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.