Reference: LeetCode
Difficulty: Easy

Problem

Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here a k-diff pair is defined as an integer pair (i, j), where i and j are both numbers in the array and their absolute difference is k.

Example: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Input: [3, 1, 4, 1, 5], k = 2
Output: 2

Input:[1, 2, 3, 4, 5], k = 1
Output: 4

Input: [1, 3, 1, 5, 4], k = 0
Output: 1

Input: [1, 2, 3, 4, 5], k = 1
Output: 4

Input: [1, 3, 1, 5, 4], k = 0
Output: 1
Exp: Only consider 1 and 1

Note:

  • The pairs (i, j) and (j, i) count as the same pair.
  • The length of the array won’t exceed 10,000.
  • All the integers in the given input belong to the range: [-1e7, 1e7].

Analysis

Hash Map

Note:

  • If k == 0, we only consider duplicates.
  • Since (i, j) and (j, i) are counted as 2, we should divide the result by 2 before returning it.
    • Actually, we don’t need to do it that way.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int findPairs(int[] nums, int k) {
  // Assume nums is not null, k >= 0
  if (k < 0) { // for LeetCode
    return 0;
  }
  Map<Integer, Integer> map = new HashMap<>(); // count map
  for (int val : nums) {
    map.put(val, map.getOrDefault(val, 0) + 1);
  }
  int numPair = 0;
  for (int val : map.keySet()) {
    // two cases: k == 0 & k != 0
    int count = map.get(val);
    if (k == 0) {
      if (count >= 2) numPair += 2; // for duplicates
      // for consistency, we have (1, 1) and (1, 1) two pairs (divided by 2 at the end).
    } else {
      if (map.containsKey(val - k)) ++numPair;
      if (map.containsKey(val + k)) ++numPair;
    }
  }
  return numPair / 2; // since (1, 2) and (2, 1) are considered the same pair
}

Optimization:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int findPairs(int[] nums, int k) {
  // Assume nums is not null, k >= 0
  if (k < 0) { // for LeetCode
    return 0;
  }
  Map<Integer, Integer> map = new HashMap<>(); // count map
  for (int val : nums) {
    map.put(val, map.getOrDefault(val, 0) + 1);
  }
  int numPair = 0;
  for (int val : map.keySet()) {
    // two cases: k == 0 & k != 0
    int count = map.get(val);
    if (k == 0) {
      if (count >= 2) ++numPair; // for duplicates
    } else {
      if (map.containsKey(val + k)) ++numPair;
    }
  }
  return numPair;
}

Time: $O(N)$
Space: $O(N)$