Pairs with difference k

101.5k
0

Given an integer array arr containing N elements and an integer k, return the total number of index pairs (i, j) satisfying:

0 <= i < j < N and |arr[i] - arr[j]| = k

Different index pairs are counted separately, even when equal values appear at multiple positions.

Example 1

Input: arr = [1, 4, 1, 4, 5], k = 3

Output: 4

Explanation: The following four index pairs have an absolute difference of 3:

(0, 1) → |1 - 4| = 3

(0, 3) → |1 - 4| = 3

(1, 2) → |4 - 1| = 3

(2, 3) → |1 - 4| = 3

Repeated values at different indices form separate pairs.

Example 2

Input: arr = [8, 16, 12, 16, 4, 0], k = 4

Output: 5

Explanation: The valid index pairs are:

(0, 2) → |8 - 12| = 4

(0, 4) → |8 - 4| = 4

(1, 2) → |16 - 12| = 4

(2, 3) → |12 - 16| = 4

(4, 5) → |4 - 0| = 4

Brute Force Approach

Every valid answer comes from two different indices. Without sorted order or stored frequency information, no candidate pair can be rejected before comparison. Complete pairwise comparison therefore provides the direct starting solution.

Restricting the second index to positions after the first index generates every unordered pair exactly once. Self-comparisons disappear, while reversed pair ordering never creates an additional count.

Algorithm

  • Return 0 when N < 2 or k < 0, because fewer than two indices cannot form a pair and an absolute difference cannot be negative.

  • Initialize count with 0 to store the number of valid index pairs.

  • Traverse index i from 0 to N - 2.

  • Traverse index j from i + 1 to N - 1, preventing self-comparison and repeated pair ordering.

  • Calculate |arr[i] - arr[j]|.

  • Increment count when the calculated difference equals k.

  • Return count after every unique pair has been checked.

Dry Run

f

f

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/* Counts index pairs through complete pair comparison. */
long long countPairsWithDiffK(
vector<int>& arr,
int k
) {
int n = arr.size();
// A negative absolute difference is impossible.
if (k < 0) {
return 0;
}
long long count = 0;
// Select the first index of every unique pair.
for (int i = 0; i < n - 1; i++) {
// Select only later indices.
for (int j = i + 1; j < n; j++) {
long long difference =
llabs(
(long long)arr[i] - arr[j]
);
// Count a pair with difference k.
if (difference == k) {
count++;
}
}
}
return count;
}
};
// Driver code to execute the solution.
int main() {
vector<int> arr = {1, 4, 1, 4, 5};
int k = 3;
Solution solution;
long long answer =
solution.countPairsWithDiffK(
arr,
k
);
cout << answer << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N²), where N represents the number of elements in arr. Every unique pair of indices is compared once.

Space Complexity: O(1), because only loop indices, the difference, and the running count are stored.

Better Approach

Quadratic work in the Brute Force Approach comes from repeatedly searching the remaining array for matching companion values. Sorting creates a predictable order and places equal values together.

After sorting, every later element is greater than or equal to the current element. For a current value x, a valid later companion must equal x + k. A lower-bound search locates the first occurrence of x + k, while an upper-bound search locates the first position after the final occurrence.

The difference between both boundaries gives the complete number of valid later positions. Sorting a separate copy preserves the original array.

Algorithm

  • Return 0 when N < 2 or k < 0.

  • Create sortedArr as a copy of arr, preserving the original input order.

  • Sort sortedArr in ascending order.

  • Initialize count with 0.

  • Traverse every index i from 0 to N - 1.

  • Calculate the required later value using:target = sortedArr[i] + k

  • Run lower-bound search inside the suffix [i + 1, N) to locate the first position containing a value greater than or equal to target.

  • Run upper-bound search inside the same suffix to locate the first position containing a value greater than target.

  • Add upperBound - lowerBound to count, because every target occurrence represents a different index pair.

  • Return count after every sorted position has been processed.

Dry Run

f

f

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
/* Finds the first position containing
a value greater than or equal to target. */
int lowerBound(
const vector<int>& values,
int left,
long long target
) {
int right = values.size();
// Search inside the range [left, right).
while (left < right) {
int mid =
left + (right - left) / 2;
// Remove values smaller than target.
if ((long long)values[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
/* Finds the first position containing
a value greater than target. */
int upperBound(
const vector<int>& values,
int left,
long long target
) {
int right = values.size();
// Search inside the range [left, right).
while (left < right) {
int mid =
left + (right - left) / 2;
// Retain target values in the left range.
if ((long long)values[mid] <= target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
public:
/* Counts index pairs after sorting an array copy. */
long long countPairsWithDiffK(
vector<int>& arr,
int k
) {
int n = arr.size();
// No pair exists when N < 2 or K < 0.
if (n < 2 || k < 0) {
return 0;
}
// Preserve original input order.
vector<int> sortedArr = arr;
// Create ascending order for binary search.
sort(
sortedArr.begin(),
sortedArr.end()
);
long long count = 0;
// Treat every position as the smaller value.
for (int i = 0; i < n; i++) {
long long target =
(long long)sortedArr[i] + k;
// Find the first target position.
int first = lowerBound(
sortedArr,
i + 1,
target
);
// Find the position after the target block.
int afterLast = upperBound(
sortedArr,
i + 1,
target
);
// Count every target occurrence.
count += afterLast - first;
}
return count;
}
};
// Driver code to execute the solution.
int main() {
vector<int> arr = {1, 4, 1, 4, 5};
int k = 3;
Solution solution;
long long answer =
solution.countPairsWithDiffK(
arr,
k
);
cout << answer << endl;

Complexity Analysis

Time Complexity: O(N log N), where N represents the number of elements in arr. Sorting requires O(N log N) time. Two O(log N) binary searches run for every one of the N positions.

Space Complexity: O(N), because a separate sorted copy stores all N array elements.

Optimal Approach

Sorting removes nested pair comparisons but still spends O(N log N) time arranging the complete array. Pair counting only requires frequencies of values from earlier indices.

During a left-to-right traversal, a current value x can form a valid pair with an earlier value equal to x - k or x + k. A Hash Map stores the frequency of every earlier value, allowing both required frequencies to contribute directly to the answer.

Frequency addition happens before insertion of the current value, ensuring one count for every unordered index pair. When k = 0, both required expressions become x, so only one frequency lookup is performed.

Algorithm

  • Return 0 when N < 2 or k < 0.

  • Initialize an empty Hash Map frequency to store value frequencies from earlier indices.

  • Initialize count with 0.

  • Traverse every value x in arr.

  • Handle k = 0 by adding frequency[x] once, because equal values form the required pairs.

  • Handle k > 0 by adding:

    • frequency[x - k], representing earlier smaller values.

    • frequency[x + k], representing earlier larger values.

  • Increase frequency[x] after both lookups, making the current index available only for later positions.

  • Return count after the complete traversal.

Dry Run

f

f

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/* Counts index pairs using frequencies
of values from earlier indices. */
long long countPairsWithDiffK(
vector<int>& arr,
int k
) {
int n = arr.size();
// No pair exists when N < 2 or K < 0.
if (n < 2 || k < 0) {
return 0;
}
// Store frequencies from earlier indices.
unordered_map<long long, long long>
frequency;
long long count = 0;
long long difference = k;
// Process each value as the later pair value.
for (int value : arr) {
long long current = value;
// Use one lookup for equal-value pairs.
if (difference == 0) {
auto same =
frequency.find(current);
if (same != frequency.end()) {
count += same->second;
}
} else {
// Count earlier smaller values.
auto smaller = frequency.find(
current - difference
);
if (smaller != frequency.end()) {
count += smaller->second;
}
// Count earlier larger values.
auto larger = frequency.find(
current + difference
);
if (larger != frequency.end()) {
count += larger->second;
}
}
// Store the current value for later indices.
frequency[current]++;
}
return count;
}
};
// Driver code to execute the solution.
int main() {
vector<int> arr = {1, 4, 1, 4, 5};
int k = 3;
Solution solution;
long long answer =
solution.countPairsWithDiffK(
arr,
k
);
cout << answer << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N) on average, where N represents the number of elements in arr. Every value requires a constant number of average O(1) Hash Map lookups and one frequency update.

Space Complexity: O(N), because the Hash Map can store frequencies for at most N distinct values.

FAQs about Pairs with difference k

1. Why does the condition j > i prevent double counting?

Every pair receives exactly one index ordering. Pair (i, j) is processed, while reversed ordering (j, i) never enters the loops.

2. How is k = 0 handled in the Hash Map Approach?

Both candidate values x - k and x + k become x. A single lookup of frequency[x] counts all earlier equal values. Two lookups would double the answer.

3. Why are both lower bound and upper bound required?
Lower bound locates the first target occurrence. Upper bound locates the first position after the final target occurrence. The difference between both indices gives the total target frequency inside the searched suffix.
4. Does sorting change the number of valid pairs?

Sorting changes element positions but preserves every element occurrence. Pair validity depends only on selected values, so the total number of valid value-occurrence combinations remains unchanged.

HashingArraysBinary Search

Read Similar Blogs

HashingData Structures

Count Distinct Elements

Given an integer array arr[] , return the count of all distinct elements in the array. Input: arr = [10, 20, 20, 10, 30, 10] Output: 3 Explanation: The different values are 10 , 20 , and 30 . 10 an...

76.5k
Arrays

Row wise traversal

Given a matrix with N rows and M columns, print all elements row by row from left to right. Input: mat = [[1, 2, 3], [4, 5, 6]] Output: 1 2 3 4 5 6 Explanation: First row prints as 1 2 3 , then sec...

61.7k
Arrays

Main Diagonal Print

Given a matrix with N rows and M columns, print all elements present on the main diagonal. Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] Output: 1 5 9 Explanation: Main diagonal cells are mat[0][0...

67.1k
Comments0