Why hashset solution is accepted whereas using hashmap getting timeout error-Finding pairs in array with difference K?

Question

I was going through a question where the problem was to find the number of pairs which makes a difference K.Below is the code for the same.In the below code I have used hashmap however it gave correct answer but for few of the scenario's I got timeout where as using HashSet all the test cases were passed.Can anyone help why using hashmap I am getting timeout error whereas in actual scenario hashmap computation is fast as compared to hashset.

static int pairs(int k, int[] arr) {

        HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
        for(int i=0;i<arr.length;i++)
            map.put(i,arr[i]);

        int count=0;
        for(int j=0;j<arr.length;j++)
        {
            if(map.containsValue(arr[j]-k))
            count++;
        }
        return count;
    }

Correct me if my understanding is wrong.Thanks in advance for the same.

Answer 1

Looking up a key in a HashMap is O(1)*, but looking up a value is O(n) -- it has to loop over every entry, one at a time, until it finds a matching value.

If you wanted analogous behavior to HashSet, you would need to put the things you've looking up into the keys, not the values. You would then use containsKey, and never actually care what there values are. Under the hood, that is in fact the implementation of HashSet that OpenJDK uses.

---

* it's actually a tad more complicated than that, but you can think of it as O(1) most of the time

Answer 2

Probably, you can write the code this way & check:-

import java.util.*; 

class GFG { 

/* Returns count of pairs with 
difference k in arr[] of size n. */
static int countPairsWithDiffK(int arr[], int n, 
                                        int k) 
{ 
    int count = 0; 
    Arrays.sort(arr); // Sort array elements 

    int l = 0; 
    int r = 0; 
    while(r < n) 
    { 
        if(arr[r] - arr[l] == k) 
        { 
            count++; 
            l++; 
            r++; 
        } 
        else if(arr[r] - arr[l] > k) 
            l++; 
        else // arr[r] - arr[l] < sum 
            r++; 
    } 
    return count; 
} 


public static void main(String[] args) 
{ 
    int arr[] = {1, 5, 3, 4, 2}; 
    int n = arr.length; 
    int k = 3; 
    System.out.println("Count of pairs with given diff is " + 
                        countPairsWithDiffK(arr, n, k)); 
} 
} 

Time Complexity: O(nlogn)