MiddleCodeOccasionalNot answered yet
Count index pairs whose value difference is at least K
Given an integer array and K >= 0, count the pairs of indices (i, j) with i <= j whose value difference |a[i] - a[j]| is at least K. When K = 0 every pair counts, including a self-pair (i, i).
Requirements:
- Better than O(n²): sort, then count with two pointers or binary search.
long long countPairsWithDiff(std::vector<int> a, int K) {
// your code here
}Write the implementation.
Sort the array. For each i, binary-search the first index whose value is at least a[i]+K; every element from there to the end forms a valid pair, so add their count. When K = 0 this counts all i <= j pairs. Total O(n log n) — far better than the O(n²) double loop.
- ✗Forgetting that K=0 includes the self-pair (i, i) in the count
- ✗Counting ordered pairs when the spec asks for i <= j (or vice versa)
- ✗Using the original (unsorted) indices and missing that sorting is allowed since only values matter
- →How would counting pairs with difference at most K (instead of at least) change the approach?
- →Why is sorting safe even though the question mentions indices?
Contents
Task
Count pairs (i, j), i <= j, with value difference at least K, better than O(n²).
Solution
long long countPairsWithDiff(std::vector<int> a, int K) {
std::sort(a.begin(), a.end());
long long total = 0;
int n = a.size();
for (int i = 0; i < n; ++i) {
long long target = static_cast<long long>(a[i]) + K; // first j with value >= a[i]+K
int j = std::lower_bound(a.begin() + i, a.end(), target) - a.begin();
total += n - j;
}
return total;
}Key points
- Sorting gives O(n log n): each
icounts partners by binary search. - With
K = 0,lower_boundpoints ata[i]itself, countingi <= jpairs. - Only
i <= jpairs are counted, not ordered pairs.
Contents
