Vultr DocsLatest Content

K-diff Pairs in an Array

Updated on 04 June, 2025
K-diff Pairs in an Array header image

Problem Statement

In this problem, you are given an array of integers named nums and an integer k. The task is to determine the number of unique k-diff pairs in the given array. A k-diff pair is defined as a tuples (nums[i], nums[j]) where:

  • The indices i and j reside within the boundaries of the array (i.e., 0 <= i, j < nums.length)
  • The indices i and j are distinct (i.e., i != j)
  • The absolute difference between the elements at these indices is exactly equal to k (i.e., |nums[i] - nums[j]| == k)

This problem requires you to consider unique pairs only. The absolute function |val| denotes the absolute value of the variable val.

Examples

Example 1

Input:

nums = [3,1,4,1,5], k = 2

Output:

2

Explanation:

There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.

Example 2

Input:

nums = [1,2,3,4,5], k = 1

Output:

4

Explanation:

There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).

Example 3

Input:

nums = [1,3,1,5,4], k = 0

Output:

1

Explanation:

There is one 0-diff pair in the array, (1, 1).

Constraints

  • 1 <= nums.length <= 104
  • -107 <= nums[i] <= 107
  • 0 <= k <= 107

Approach and Intuition

To solve the problem of finding k-diff pairs in an array, we can follow several steps:

  1. Use a hash map or a dictionary to count unique numbers in the array. This will help to efficiently check whether a certain element exists in the array, which will be useful to find pairs with the specified difference k.

  2. For k = 0, we need to find elements that appear at least twice in the array. Therefore, we can directly look for any numbers in our count map that have a frequency greater than or equal to 2.

  3. For k > 0, for each unique number in the array, check if this number plus k exists in the hash map. If it does, then a valid k-diff pair exists. It's important to note that looking for both num + k and num - k can lead to counting pairs twice, so generally only one direction is needed unless specified otherwise.

  4. Maintain a set or another hash map to keep track of pairs we have counted. This helps in keeping the pairs unique. For each valid pair found, add it to the set.

  5. The count of unique pairs in the set would be the final answer.

The approach carefully handles all edge cases, such as potential duplicates in the array and the presence of negative numbers, by leveraging the dictionary to handle uniqueness and the check conditions. The computational complexity is linear with regard to the number of elements in the input array, making it efficient even for larger inputs within the problem's constraints.

Solutions

  • Java
  • Python
java 
public class Solution {
    public int countPairs(int[] nums, int k) {

        int pairCount = 0;

        HashMap <Integer,Integer> numCounts = new HashMap<>();
        for (int num: nums) {
            numCounts.put(num, numCounts.getOrDefault(num, 0) + 1);
        }


        for (Map.Entry <Integer, Integer> entry: numCounts.entrySet()) {
            int numKey = entry.getKey();
            int countValue = entry.getValue();
            if (k > 0 && numCounts.containsKey(numKey + k)) {
                pairCount++;
            } else if (k == 0 && countValue > 1) {
                pairCount++;
            }
        }
        return pairCount;
    }
}

The provided Java solution efficiently counts the number of k-diff pairs in an array, where a k-diff pair consists of two integers with a difference equal to a given value k. Here's how the solution operates:

  • The solution defines the countPairs method which accepts an array of integers nums and an integer k.
  • It initializes the pairCount variable to track the number of valid pairs.
  • A HashMap named numCounts is used to store the frequency of each number in the nums array.
  • The first loop populates the numCounts HashMap by iterating over each number in the nums array and updating the count for each encountered number.
  • A subsequent loop checks for pairs. It iterates through each entry in numCounts:
    • If k is greater than 0, it checks if the number incremented by k is a key in the numCounts. If it is, pairCount is incremented.
    • If k equals 0, it checks for numbers that appear more than once, as they form a pair with themselves. If such a condition is true, pairCount is incremented.
  • Finally, the method returns pairCount, representing the total number of k-diff pairs in the array.

This solution benefits from using a HashMap to monitor the frequency of each item, allowing quick checks for the k-diff condition in constant time, resulting in a more efficient approach than a straightforward nested loop comparison.

python 
from collections import Counter

class Solution:
    def countPairs(self, numbers, diff):
        count = 0
        freq = Counter(numbers)
        for num in freq:
            if diff > 0 and num + diff in freq:
                count += 1
            elif diff == 0 and freq[num] > 1:
                count += 1
        return count

This solution involves counting unique k-diff pairs in an array where k is defined as an input difference diff and the array elements are supplied in numbers. The method countPairs solves the problem using a dictionary to count occurrences of each number in the input array using Python's Counter from the collections module.

  • Initialize a variable count to zero to keep track of the number of valid pairs.
  • Create a frequency dictionary freq that maps each number to its frequency in the array.
  • Iterate through each unique number num in the frequency dictionary.
    • If diff is greater than 0 and the number num + diff exists in freq, increment count.
    • If diff is 0 (looking for pairs of the same numbers with distance 0), and a number appears more than once, increment count.
  • Finally, return the count which represents the number of k-diff pairs in the array.

This approach effectively handles the detection of pairs differing by a specific value with an efficient O(n) complexity using hash map operations for constant time look-up.

Comments

No comments yet.