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.

Any specific reason to use `HashMap`? What is the amount of data? — Shubhendu Pramanik, Nov 24 '18 at 04:29
Actually I thought the solution using hashmap initially but for few cases it failed that is when I went for hashset. Eager to know the reason of failure using hashmap. The size of an array is less than 10^5 and the values it can have 2^31-1. — Pratyush Mayank, Nov 24 '18 at 04:48

score 1 · Answer 1 · answered Nov 24 '18 at 06:29

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

score 0 · Answer 2 · answered Nov 24 '18 at 04:58

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)

Thanks for the help but I already have an accepted answer for the above problem using hashset. My concern is why using hashmap I was getting timeout. — Pratyush Mayank, Nov 24 '18 at 05:33
This [https://stackoverflow.com/questions/2773824/difference-between-hashset-and-hashmap] would definitely help you! Just have a look once. — Abhinav, Nov 24 '18 at 07:06

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

2 Answers2