532.K-diffPairsinanArray.py

"""
    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
        - a <= b
        - b - a == k

    Example:
    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:
    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:
    Input: nums = [1,3,1,5,4], k = 0
    Output: 1
    Explanation: There is one 0-diff pair in the array, (1, 1).

    Example:
    Input: nums = [1,2,4,4,3,3,0,9,2,3], k = 3
    Output: 2

    Example:
    Input: nums = [-1,-2,-3], k = 1
    Output: 2

    Constraints:
        - 1 <= nums.length <= 104
        - -107 <= nums[i] <= 107
        - 0 <= k <= 107
"""
#Difficulty: Medium
#59 / 59 test cases passed.
#Runtime: 5628 ms
#Memory Usage: 15.6 MB

#Runtime: 5628 ms, faster than 5.01% of Python3 online submissions for K-diff Pairs in an Array.
#Memory Usage: 15.6 MB, less than 33.73% of Python3 online submissions for K-diff Pairs in an Array.

class Solution:
    def findPairs(self, nums: List[int], k: int) -> int:
        count = set()
        nums.sort()
        length = len(nums)
        for i in range(length):
            for j in range(i+1, length):
                if abs(nums[i] - nums[j]) == k:
                    count.add((min(nums[i], nums[j]), max(nums[i], nums[j])))
                    break
        return len(count)