Practice › Hashing & Two Pointers
Count Pairs with Difference K
Medium · Hashing & Two Pointers · Asked at Amazon, Microsoft, Goldman Sachs
Count the number of distinct value pairs (x, y) from the array with y − x = k. Each pair of values counts once, even if the values repeat.
Input
First line: n. Second line: n integers. Third line: k.
Output
The number of distinct pairs.
Constraints
- 1 ≤ n ≤ 10^5
- 1 ≤ k ≤ 10^9
Example 1
Input
5 1 5 3 4 2 3
Output
2
Example 2
Input
4 1 1 1 2 1
Output
1
Hints
- Repeated values don't create new pairs — work with the set of distinct values.
- For each distinct x, the pair exists exactly when x + k is also in the set.
Approach
Since k ≥ 1, a pair (x, x + k) is determined by its smaller value x. Put the values in a hash set and count the x for which x + k is also present. Each distinct pair is counted once, however many copies the array holds.
Complexity: O(n) average time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
unordered_set<long long> s;
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
s.insert(x);
}
long long k;
cin >> k;
int count = 0;
for (long long x : s)
if (s.count(x + k)) count++;
cout << count << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n = data[0]
s = set(data[1 : n + 1])
k = data[n + 1]
print(sum(1 for x in s if x + k in s))Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Set<Long> s = new HashSet<>();
for (int i = 0; i < n; i++) s.add(sc.nextLong());
long k = sc.nextLong();
int count = 0;
for (long x : s)
if (s.contains(x + k)) count++;
System.out.println(count);
}
}Solve Count Pairs with Difference K online · All practice problems