Problem Statement in English

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

Approach

  • $O(n)$ time and $O(n)$ space

    This is fairly straightforward. We build an index of all elements in nums and their counts. Then we iterate through the index and for each element, we check if its required counterpart exists in the index. If it does, we increment the answer by 1. We also keep track of the pairs we have already seen to avoid duplicates.

  • $O(nlogn)$ time and $O(1)$ space

    This is a bit more tricky. We first sort the array, as we intend to utilise the 2 Pointer Technique.

    Next, we iterate through the array, considering each element as the first element of the pair. We then use the 2 pointer technique to find the second element of the pair.

    We ensure that the second element is to the right of the first element, and that the difference between the two elements is exactly $k$. We also ensure that the second element is unique, to avoid duplicates.

Solution in Python

  • $O(n)$ time and $O(n)$ space

class Solution:
    def findPairs(self, nums: List[int], k: int) -> int:
        store = Counter(nums)

        ans = 0
        used = set()

        for key, value in store.items():
            if k == 0 and value > 1:
                ans += 1
                continue
            elif k == 0 and value <= 1:
                continue

            required = 0

            if key < 0:
                required = key + k
            else:
                required = key - k

            if (required, key) in used:
                continue

            res = store.get(required, 0)
            if res > 0:
                ans += 1
                used.add((key, required))

        return ans
  • $O(nlogn)$ time and $O(1)$ space

class Solution:
    def findPairs(self, nums: List[int], k: int) -> int:
        ans = 0
        nums.sort()

        l, r = 0, len(nums) - 1

        # we need to move `l` to the correct spot
        while nums[r] - nums[l] > k:
            l += 1
        # l is now at the correct position

        # ensure l is before r and
        # l is >= 0 (must be a valid index)
        while l >= 0 and (l < r):
            # if the diff is k
            if nums[r] - nums[l] == k:
                # add to answers
                ans += 1

            # keep moving `r` leftwards
            # until it's pointing at a new number
            #
            # ensure that `r` is within the range of nums
            # decrement it once to ensure we have a valid reference
            # for what the last number it was pointing at was
            r -= 1
            while r > 0 and r + 1 < len(nums) and nums[r] == nums[r + 1]:
                r -= 1

            # move `l` leftwards until it's to the left of `r`
            # also ensure that
            # - it's within range of `nums`
            # - it's difference with the number pointed to by `r` is < `k`
            while (l > 0 and nums[r] - nums[l] < k) or l >= r:
                l -= 1

        return ans

Complexity

  • Time: $O(n)$ or $O(nlogn)$

  • Space: $O(n)$ or $O(1)$

And we are done.