{x}
blog image

K-diff Pairs in an Array

Given an array of integers nums and an integer k, return the number of unique k-diff pairs in the array.

A k-diff pair is an integer pair (nums[i], nums[j]), where the following are true:

  • 0 <= i, j < nums.length
  • i != j
  • |nums[i] - nums[j]| == k

Notice that |val| denotes the absolute value of val.

 

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

Solution Explanation

The problem asks to find the number of unique pairs in an array nums where the absolute difference between the elements of the pair is equal to k.

Approach 1: Using Hash Sets

This approach leverages the properties of hash sets for efficient lookups. We use two hash sets: vis to store visited numbers and ans to store unique k-diff pairs. The algorithm iterates through the input array:

  1. Check for pairs: For each number v in nums, it checks if v - k and v + k are present in the vis set. If either is found, it means a k-diff pair exists, and the corresponding number (v - k or v) is added to the ans set (to ensure uniqueness).

  2. Mark as visited: After checking, the current number v is added to the vis set.

  3. Return the count: Finally, the size of the ans set (which contains the unique k-diff pairs) is returned.

Time Complexity: O(N), where N is the length of nums. Hash set lookups and insertions are on average O(1).

Space Complexity: O(N) in the worst case, to store the vis and ans sets.

Approach 2: Sorting and Two Pointers (for Rust solution)

The Rust solution uses a different approach:

  1. Sort the array: The input array nums is first sorted. This enables the use of two pointers for efficient searching.

  2. Two-pointer traversal: Two pointers, left and right, are initialized. left starts at index 0, and right starts at index 1.

  3. Check for k-diff pairs: The algorithm compares the absolute difference between nums[left] and nums[right] with k.

    • If the difference is equal to k, a k-diff pair is found, the counter res is incremented, and both pointers are moved to skip duplicate elements.
    • If the difference is less than k, right is moved to potentially find a larger difference.
    • If the difference is greater than k, left is moved to potentially find a smaller difference.

  4. Return the count: The final value of res represents the number of unique k-diff pairs.

Time Complexity: O(N log N) dominated by the sorting step, where N is the length of nums. The two-pointer traversal is O(N).

Space Complexity: O(1). The algorithm uses only a few constant extra variables. In-place sorting is assumed.

Code Explanation (Python, Java, C++, Go)

The Python, Java, C++, and Go solutions all implement the hash set approach. The code structure is very similar across these languages:

  • They all initialize two hash sets (vis and ans).
  • They iterate through the input array.
  • Inside the loop, they check for the existence of v - k and v + k in vis.
  • They add the found numbers to ans and the current number to vis.
  • Finally, they return the size of ans.

The differences are mainly in the syntax and specific hash set implementations used by each language. For example, Python uses set, Java uses HashSet, C++ uses unordered_set, and Go uses map[int]bool.

Code Explanation (Rust)

The Rust solution is unique because it employs the sorting and two-pointer approach. The code explicitly handles duplicate numbers to ensure counting only unique pairs. The while loop manages the movement of the pointers, and the conditional statements determine the appropriate adjustments based on the difference between the elements pointed to. The use of i32::abs() calculates the absolute difference.