## Interview Question

**Country:**United States

**Interview Type:**Phone Interview

It covers the [x, x, .... ], K>0 case

but I think it misses the [x, x, ... ], K=0 case.

Maybe this:

```
public static int getDiffPair(int a[] , int diff){
HashMap<Integer,Integer> hashMap = new HashMap<Integer,Integer>();
int count = 1;
for(int i = 0;i<a.length;i++){
if(hashMap.containsKey(a[i])){
count = hashMap.get(a[i]);
hashMap.put(a[i], ++count);
}else{
hashMap.put(a[i], 1);
}
}
count = 0;
for(int j = 0;j<a.length;j++){
if(hashMap.containsKey(a[j]+diff)){
count+=hashMap.get(a[j]+diff) - (!diff ?1:0); //changed
}
}
return count;
}
```

First of all, what I would do, was to use a

`HashMap<Integer, LinkedList<Integer>> hashMap;`

So that I could also store the location of other index. If you just need the count, then use hashMap.get(i).size(). This way you can also identify the pairs, as well as the number of repetitions.

However, the array in your example is sorted. In such a case, you can actually solve it in O(1) space and O(N + M) time where "N" is the length of input, and "M" is the number of pairs of indices with a difference equal to "K". I used the idea from a O(1) space solution for 3-sum problem (google it).

Keep two pointers pos_1 <= pos_2. If array is sorted ascendingly, then array[pos_2] >= array[pos_1].

1- Check cmp = array[pos_2] - array[pos_1].

2- If "cmp" is smaller than "k", the desired difference, increase pos_2 to obtain a larger difference. Else, decrease pos_1.

3- If cmp == 0, then you already found a pair [pos_1, pos_2]. All you need to do is to resolve the repeated element case. For that, increase pos_1 until the value changes. Do the same for pos_2. Then generate all the possible tuples (pos_1, pos_2) for the ranges you found.

Here is the java code.

```
public static void main(String[] args) {
int[] arr = {1, 1, 5, 5, 5, 6, 9, 16, 27};
listKdiff(arr, 4);
}
public static void listKdiff(int[] arr, int k) {
int pos_1 = 0;
int pos_2 = 0;
while(pos_2 < arr.length) {
int cmp = arr[pos_2] - arr[pos_1];
if (cmp < k) {
pos_2++;
}
else if (cmp > k) {
pos_1++;
}
else {
// length of the subarrays of equal values starting from pos_1 and pos_2
int len1 = 0, len2 = 0;
while (arr[pos_1 + len1] == arr[pos_1]) {
len1++;
}
while (arr[pos_2 + len2] == arr[pos_2]) {
len2++;
if (len2 + pos_2 == arr.length - 1) {
break;
}
}
// print all pairs of duplicates
for (int i = 0; i < len1; i++) {
int a = pos_1 + i;
for (int j = 0; j < len2; j++) {
int b = pos_2 + j;
System.out.println("[" + a + ", " + b + "]");
}
}
pos_1 = pos_1 + len1;
pos_2 = pos_2 + len2;
}
}
}
```

This is the output I got. The first 6 pairs corresponds to combinations of (1, 5) and the last three are combinations of (5, 9) (I printed the indices):

```
[0, 2]
[0, 3]
[0, 4]
[1, 2]
[1, 3]
[1, 4]
[2, 6]
[3, 6]
[4, 6]
```

We all spend time working on these types of problems. The reason is to learn and give feedback. While everyone is entitled to down/up voting whatever they want, it is best if a feedback is provided. How on earth would you downvote a correct solution? Unless you found and error and would like to share, in such a case, your efforts would be much appreciated.

1) Format your code correctly

2) Name your variables properly

3) Comment your code unless it's obvious what you are doing

4) Explain your code (you talk briefly of how you would solve it for unsorted arrays, but then you put code for sorted arrays without any explanation)

5) Explain runtime of your code

6) Generally, save the time of readers (don't worry about your time)

And it wasn't me who downvoted you.

The problem only required you to find how many pairs there were (i.e. a count) so no need to print out pairs :)

Some people are being rough on here on my question. It's not so difficult I think as I already got an O(2n) solution which is fine for interview purposes.

Cool idea. +1

You saved space O(1) by sacrificing time O(n^2). It is a legitimate, possible use case.

Thanks.

Actually, it is not O(N^2) as long as the number of pairs of indices is not O(N^2). In each iteration of the while loop, I increase either pos_1 or pos_2. So at most, there will be 2N iterations if there are no repeated elements.

It can be best said that the running time is O(N + M) where M is the number of pairs. In the example above, M = 9.

This idea is from 3-SUM problem. But only works on sorted arrays.

Remove the nested for loop. Instead of making all pairs, simply add the following line

`count += len1 * len2;`

In the main while loop, in every iteration either pos_1 or pos_2 or both are increased by at least "1". So it will take at most "2N" iterations.

When printing the pairs, the reason you get O(N^2) is something like this:

`int[] arr = {1, 1, 1, 1, 5, 5, 5, 5, 5, 5}`

where there are "NxM" pairs to list (N = 4 and M = 6 in this example). But we if you only need the count, then simply add "N * M" to the count and increase pos_1 by N and pos_2 by M.

```
public static int getDiffPair(int a[] , int diff){
HashMap<Integer,Integer> hashMap = new HashMap<Integer,Integer>();
int count = 1;
for(int i = 0;i<a.length;i++){
if(hashMap.containsKey(a[i])){
count = hashMap.get(a[i]);
hashMap.put(a[i], ++count);
}else{
hashMap.put(a[i], 1);
}
}
count = 0;
for(int j = 0;j<a.length;j++){
if(hashMap.containsKey(a[j]+diff)){
count+=hashMap.get(a[j]+diff);
hashMap.put(a[i],0);
}
}
return count;
}
```

Oh, I figured out how to do it in two passes, but i'm still wondering if you can do it with only one.

```
public static int arrayPairDifference(int[] a, int k)
{
HashMap<Integer, Integer> hashMap = new HashMap<>();
int count = 0;
for (int i = 0; i < a.length; i++)
{
hashMap.put(i, a[i]);
}
for (int j = 0; j < a.length; j++)
{
if (hashMap.containsValue(a[j] + k))
{
count++;
}
}
return count;
}
```

with duplication, the problem became quiet tricky.

There are couples of solutions for this, it all depends if we can change the original data, if we could use extra space, etc.

1) the safest way(no extra space, and easy to code) is that we use two-layer loop.

for ith element a[i], we check how many k-a[i] in the rest of subarray. No extra space, for small array, it should be the fast way, even it's time complexity is O(n).

2) if we could change the original input array, we could first sort the array(if it's not sorted), for each element a[i], we do binary search on subarray a[i+1]...a[n-1]. we need to do this twice, since we want to find how many k-a[i] in the subarray, we use adapted binary search algorithm to find the lowest index and highest index with the value of k-a[i], the time complexity will be O(nlg(n)), but it's error-prone. For example: a=[2 6 6 6 9], run this on array a.

3) use a extra hashmap, this is very tricky if there are duplicated elements, for example, for array: a=[2 2 2 2] and K=4, the resulting number of pairs should be 6. we could create a map, with the keys be element values, and values are the number of occurrences, when we scan through the array, for element a[i], first we need to decrement the value of hashMap[a[i]] by one, and then count how many k-a[i] there. otherwise, you will get 16 instead of 6 for the input array a=[2,2,2,2] and K=4. the time complexity for this algo is O(n).

- Manish March 12, 2014