algoadvance

Leetcode 532. K

Problem Statement

Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here, a k-diff pair is defined as an integer pair (i, j), where i and j are indices in the array, such that |nums[i] - nums[j]| = k and i != j.

Note:

• The pairs (i, j) and (j, i) are considered the same, thus should only be counted once.

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).

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).

Input: nums = [1, 3, 1, 5, 4], k = 0
Output: 1
Explanation: There is one 0-diff pair in the array, (1, 1).

Clarifying Questions

1. Can the elements of the array be negative?
   • Yes, the array can contain negative elements.
2. What is the range of integers in the array and the value of k?
   • The array length is between 1 and 10^4, and the values inside the array and k are between -10^7 to 10^7.
3. Do array elements need to be distinct?
   • No, array elements may not be distinct.

Strategy

1. Special Case (k = 0):
   • When k is zero, we are looking for duplicates in the array.
2. General Case (k > 0):
   • Use a HashSet to track the elements we have seen and another HashSet to track the unique pairs that satisfy the condition |nums[i] - nums[j]| = k.

Code

import java.util.*;

public class KDiffPairs {
    public int findPairs(int[] nums, int k) {
        if (k < 0) return 0;  // Since absolute difference cannot be negative

        Set<Integer> set = new HashSet<>();
        Set<Integer> seenPairs = new HashSet<>();

        for (int num : nums) {
            if (set.contains(num + k)) {
                seenPairs.add(num);
            }
            if (set.contains(num - k)) {
                seenPairs.add(num - k);
            }
            set.add(num);
        }
        return seenPairs.size();
    }

    public static void main(String[] args) {
        KDiffPairs solution = new KDiffPairs();
        int[] nums1 = {3, 1, 4, 1, 5};
        int k1 = 2;
        System.out.println(solution.findPairs(nums1, k1));  // Output: 2

        int[] nums2 = {1, 2, 3, 4, 5};
        int k2 = 1;
        System.out.println(solution.findPairs(nums2, k2));  // Output: 4

        int[] nums3 = {1, 3, 1, 5, 4};
        int k3 = 0;
        System.out.println(solution.findPairs(nums3, k3));  // Output: 1
    }
}

Time Complexity

• The time complexity is O(n), where n is the number of elements in the array since we only traverse the array once and the HashSet operations (insert, search) are average O(1).

Space Complexity

• The space complexity is O(n) because in the worst case we may store all elements in the HashSet.

Feel free to ask more clarifying questions or provide feedback on this strategy!

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?