LeetCode 532: K-diff Pairs in an Array Solution in Python – A Step-by-Step Guide

What Is LeetCode 532: K-diff Pairs in an Array?

In LeetCode 532: K-diff Pairs in an Array, you’re given an array of integers nums and an integer k, and your task is to find the number of unique pairs (i, j) where i < j and the absolute difference |nums[i] - nums[j]| equals k. For example, with nums = [3, 1, 4, 1, 5] and k = 2, there are 2 pairs: (1, 3) and (3, 5). This problem tests pair-finding strategies, related to LeetCode 1: Two Sum for hash map techniques.

Problem Statement

• Input:
• nums (List[int]): Array of integers.
• k (int): Target difference.
• Output: Integer—number of unique pairs with difference k.
• Rules: Pairs (i, j) must have i < j; count unique pairs only.

Constraints

• 1 <= nums.length <= 10⁴
• -10⁷ <= nums[i] <= 10⁷
• 0 <= k <= 10⁷

Examples

• Input: nums = [3,1,4,1,5], k = 2
• Output: 2
• Pairs: (1, 3), (3, 5).
• Input: nums = [1,2,3,4], k = 1
• Output: 4
• Pairs: (1, 2), (2, 3), (3, 4).
• Input: nums = [1,1,1,1,1], k = 0
• Output: 1
• One unique pair (any two 1s).

Understanding the Problem: Counting K-diff Pairs

To solve LeetCode 532: K-diff Pairs in an Array in Python, we need to count unique pairs of indices (i, j) in nums where i < j and |nums[i] - nums[j]| = k. A naive approach might check all n² pairs, but with up to 10⁴ elements, we need efficiency. Since pairs are unordered in value but ordered by index, we must ensure uniqueness (e.g., (1, 3) and (3, 1) count as one). We’ll explore:

• Best Solution (Hash Map with Single Pass): O(n) time, O(n) space—fast and elegant.
• Alternative Solution (Sorting with Two Pointers): O(n log n) time, O(1) space—intuitive but requires sorting.

Let’s dive into the hash map solution with a friendly breakdown!

Best Solution: Hash Map with Single Pass

Why Hash Map Wins

The hash map with single pass is the best for LeetCode 532 because it processes the array in O(n) time, using a hash map to track numbers and find pairs with difference k in one go, with O(n) space. It’s like keeping a lookout list and spotting matches as you scan!

How It Works

Think of this as a number lookout game:

• Step 1: Initialize Hash Map:
• Use a dictionary seen to store numbers and their counts or presence.
• Step 2: Single Pass:
• For each num:
• Check if num + k or num - k is in seen.
• If found, add pair to result (track uniqueness).
• Add num to seen.
• Step 3: Handle k = 0:
• If k = 0, count pairs of same numbers (e.g., two 1s).
• Step 4: Return Count:
• Number of unique pairs.
• Why It Works:
• Hash map lookups are O(1).
• Single pass avoids redundant checks.

It’s like a pair-spotting ninja!

Step-by-Step Example

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

• Init: seen = {}, pairs = set().
• Step 1: Iterate:
• 3: Check 5 (not seen), 1 (not seen), seen = {3: 1}.
• 1: Check 3 (seen, add (1, 3)), -1 (not seen), seen = {3: 1, 1: 1}.
• 4: Check 6 (not seen), 2 (not seen), seen = {3: 1, 1: 1, 4: 1}.
• 1: Check 3 (seen, (1, 3) already counted), -1 (not seen), seen = {3: 1, 1: 2, 4: 1}.
• 5: Check 7 (not seen), 3 (seen, add (3, 5)), seen = {3: 1, 1: 2, 4: 1, 5: 1}.
• Step 2: pairs = {(1, 3), (3, 5)}.
• Result: 2.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

Copy codeclass Solution:
    def findPairs(self, nums: List[int], k: int) -> int:
        # Step 1: Initialize hash map and pairs set
        seen = {}
        pairs = set()

        # Step 2: Single pass through array
        for num in nums:
            # Check for num + k
            if num + k in seen:
                pairs.add((num, num + k))
            # Check for num - k
            if num - k in seen:
                pairs.add((num - k, num))
            # Add current number
            seen[num] = seen.get(num, 0) + 1

        # Step 3: Adjust for k = 0
        if k == 0:
            count = sum(1 for v in seen.values() if v > 1)
            return count

        # Step 4: Return number of unique pairs
        return len(pairs)

• Lines 4-5: Hash map for counts, set for unique pairs.
• Lines 8-14: For each number:
• Check if num + k or num - k seen, add pair (small, large).
• Increment count in seen.
• Lines 17-19: If k = 0, count numbers with frequency > 1.
• Line 22: Return pair count.
• Time Complexity: O(n)—single pass.
• Space Complexity: O(n)—hash map and pairs set.

It’s like a k-diff pair counter!

Alternative Solution: Sorting with Two Pointers

Why an Alternative Approach?

The sorting with two pointers solution sorts the array first, then uses two pointers to find pairs with difference k in O(n log n) time and O(1) space (excluding sort space). It’s intuitive but slower due to sorting. Great for two-pointer fans!

How It Works

Picture this as a sorted number chase:

• Step 1: Sort array.
• Step 2: Two pointers (left, right):
• Move pointers to find nums[right] - nums[left] = k.
• Skip duplicates for uniqueness.
• Step 3: Count valid pairs.

It’s like a sorted pair chaser!

Step-by-Step Example

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

• Step 1: Sort: [1, 1, 3, 4, 5].
• Step 2: Two pointers:
• left = 0 (1), right = 1 (1): 1-1=0 < 2, right += 1.
• left = 0 (1), right = 2 (3): 3-1=2, count += 1, left += 1.
• left = 1 (1), right = 2 (3): 3-1=2 (duplicate, skip), left += 1.
• left = 2 (3), right = 3 (4): 4-3=1 < 2, right += 1.
• left = 2 (3), right = 4 (5): 5-3=2, count += 1, left += 1.
• Result: 2.

Code for Two Pointers Approach

Copy codeclass Solution:
    def findPairs(self, nums: List[int], k: int) -> int:
        # Step 1: Sort array
        nums.sort()
        n = len(nums)
        count = 0

        # Step 2: Two pointers
        left = 0
        right = 1

        while right < n:
            diff = nums[right] - nums[left]
            if left >= right:
                right += 1
            elif diff < k:
                right += 1
            elif diff > k:
                left += 1
            else:  # diff == k
                count += 1
                left += 1
                right += 1
                # Skip duplicates
                while left < n and nums[left] == nums[left-1]:
                    left += 1
                while right < n and right - 1 > 0 and nums[right] == nums[right-1]:
                    right += 1

        # Step 3: Return count
        return count

• Line 4: Sort array.
• Lines 8-23: Two pointers adjust to find k-diff, skip duplicates.
• Line 26: Return pair count.
• Time Complexity: O(n log n)—sorting dominates.
• Space Complexity: O(1)—no extra space.

It’s a sorted pair seeker!

Comparing the Two Solutions

• Hash Map (Best):
• Pros: O(n), O(n), fast.
• Cons: Extra space.
• Two Pointers (Alternative):
• Pros: O(n log n), O Warehouse(1), space-efficient.
• Cons: Slower due to sort.

Hash map wins for speed!

Additional Examples and Edge Cases

• [1, 2], k = 1: 1.
• [1, 1], k = 0: 1.
• [1, 3, 5], k = 1: 0.

Hash map handles them all!

Complexity Recap

• Hash Map: Time O(n), Space O(n).
• Two Pointers: Time O(n log n), Space O(1).

Hash map’s the efficiency champ!

Key Takeaways

• Hash Map: Lookup magic—learn at Python Basics!
• Two Pointers: Sorted simplicity.
• Arrays: Pairs are fun.
• Python: Dicts or pointers, your pick!

Final Thoughts: Count Those Pairs!

LeetCode 532: K-diff Pairs in an Array in Python is a delightful pair-finding challenge. Hash map with single pass is your fast track, while sorting with two pointers offers a sorted twist. Want more? Try LeetCode 1: Two Sum or LeetCode 167: Two Sum II - Input Array Is Sorted. Ready to pair up? Head to Solve LeetCode 532 on LeetCode and count those k-diff pairs today!