2

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!

idude
  • 4,654
  • 8
  • 35
  • 49

5 Answers5

3

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.

Ling Zhong
  • 1,744
  • 14
  • 24
  • 1
    It's not an overkill. It correctly handles both array with duplicate numbers and with distinct numbers with same O(n) runtime. Which is important as it is not explicitly specified in the question. i.e. it handles [4, 4, 4], k = 0 case correctly. – Ling Zhong Oct 18 '15 at 17:56
  • Also, SetHash solution breaks for trivial case: [4], k = 0 – Ling Zhong Oct 18 '15 at 18:05
2

With HashSet (which internally uses HashMap) we can assume that its contains method is close to O(1) so you could

  1. fill such set with all elements
  2. iterate over elements and calculate values for +4 and -4 differences
  3. check if these values exist in set.
  4. divide result by 2 since you will get true for pairs 1,5 and 5,1 which in reality is one pair.

As shown by Óscar López you can improve it by calculating only one of +4 and -4 and skip last step

Community
  • 1
  • 1
Pshemo
  • 122,468
  • 25
  • 185
  • 269
2

In fact, it can be solved using just a Set: we have to find if the set contains another element whose difference with the current results in k. Try the following solution, it works assuming that there are at least two elements in an input with no duplicates, and doesn't waste space for a non-needed value as would be the case if we used a HashMap for this problem:

int k = 4;
int howMany = 0;
Set<Integer> set = new HashSet<>(Arrays.asList(1, 4, 5, 7, 8, 9));

System.out.printf("k = %d%n", k);   

for (Integer n : set) {
    if (set.contains(n - k)) {
        howMany++;
        System.out.printf("(%d - %d) = k%n", n, n - k);
    }
}

System.out.printf("k appears %d times%n", howMany);

The above results in the following output:

k = 4
(5 - 1) = k
(8 - 4) = k
(9 - 5) = k
k appears 3 times
Óscar López
  • 232,561
  • 37
  • 312
  • 386
1

The following method works even if the array contains duplicates. It implements Pshemo's final algorithm (without the duplicate work and without the division by 2).

First, it stores the contents of the original array in a hashmap. The original value is the key, and the number of times the original value appears in the array is the value of the hashmap. This phase has a runtime O(number of items in the original list), and uses storage O(number of distinct items in the original list).

Second, it loops through the hashmap, and finds any items that are (delta = 4) greater than the item being considered. It does some math to increment the result tally. It has a special case to handle (delta == 0) scenarios, to deal with the issue Ling Zhong mentioned. This phase has a runtime O(number of distinct items in the original list).

public class Solution {
    public int countDifferences(int delta, int[] array) {
        if (array == null) {
            return 0;
        }
        // Load the contents of the array into a hashmap.
        // This process loses the sorting.
        HashMap<Integer, Integer> choices = new HashMap<>();
        for (int arrayItem : array) {
            if (choices.containsKey(arrayItem)) {
                choices.put(arrayItem, 1 + choices.get(arrayItem));
            } else {
                choices.put(arrayItem, 1);
            }
        }

        // Count the result.
        int result = 0;
        for(Map.Entry<Integer, Integer> e : choices.entrySet()) {
            Integer key   = e.getKey();
            Integer value = e.getValue();
            if (delta == 0) {
                result += value * (value - 1) / 2; // add summorial(value - 1)
            } else {
                if (choices.containsKey(key + delta)) {
                    result += value * choices.get(key + delta);
                }
            }
        }
        return result;
    }
}
Community
  • 1
  • 1
Jasper
  • 409
  • 4
  • 17
0

You can achieve this in single iteration. Apply logic like this, when start iterating say suppose u have a hashmap with k,v pair Ex. 1,dummyvalue 4,dummyvalue 5, dummy value

And say suppose ur k=4 So when start iterating over map u will get say first 1 so do it like 1+k i.e 1+4 i.e 5 so look back in ur data structure or map for key=5 map.get(5) if map returns the value update another map or another data structure which is holding ur count ok k say suppose we have a map with k=4 so its value will b something like this count = count +1 if we get the key which over here is 4.

deepakkumarmalviya
  • 1
  • 1