idude idude - 1 month ago 7
Java Question

How to solve this using hashmaps?

Suppose you're given a list of the following values:

[1,4,5,7,8,9]


and you're given that
k=4
where
k
is the difference between two array elements. How would you find how many times
k
appears? For example, in this list
k
appears 3 times
[(5-1),(8-4),(9-5)]


I was able to solve this using two for loops but that requires
O(n^2)
time. I heard this could be solved using hashmaps, but am unsure how to would implement it?

Any ideas would be greatly appreciated!

Answer

The idea to is to store all the possible differences between the k and each value in the input array (numbers). Then count the number of values in the input array that fits the difference.

This will work:

public class Solution {
    public int twoSum(int[] numbers, int k) {
        if (numbers == null) {
            return null;
        }
        int count = 0;
        HashMap<Integer, Integer> difference = new HashMap<Integer, Integer>();
        for (int i = 0; i < numbers.length; i++) {
            difference.put(k - numbers[i], i);
        }
        for (int i = 0; i < numbers.length; i++) {
            int cur = -numbers[i];
            if (difference.containsKey(cur) && difference.get(cur) != i) {
                count++;
            }
        }
        return count;
    }
}

The catch is to have difference.get(cur) != i condition in place (where i is the index cur) to avoid the case of having k = 0 and each value would form a pair with itself.

Comments