algoadvance

Leetcode 532. K

Problem Statement

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 conditions are met:

Notice that val denotes the absolute value of val.

Clarifying Questions

  1. What constitutes a unique pair?
    • The pair (nums[i], nums[j]) is considered unique for distinct values of i and j.
  2. Can the array contain duplicate elements?
    • Yes, the array can contain duplicate elements.
  3. What is the expected range for nums and k?
    • Generally, for LeetCode problems, nums may contain up to 10^4 elements, and k could be in the range from 0 to 10^7.
  4. What if the array is empty or k is negative?
    • An empty array should return 0 because no pairs can be formed. If k is negative, no pair with a negative absolute difference can exist, so the result should be 0.

Strategy

We can solve this problem efficiently using a hash map (unordered_map). The strategy involves the following steps:

  1. Input Validation: Check if the input array is empty or k is negative.
  2. Frequency Counter: Use a hash map to count the frequency of each number in the array.
  3. Count Unique Pairs:
    • If k == 0, count the numbers that appear more than once because the pair (x, x) with |x - x| == 0 is valid.
    • If k > 0, for each unique number num in the array, check whether num + k exists in the array using the hash map to ensure O(1) look-up time.

Code

Here’s the C++ implementation of the above strategy:

#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        if (nums.empty() || k < 0) return 0;  // No pairs possible for invalid inputs

        unordered_map<int, int> numCount;
        for (int num : nums) {
            numCount[num]++;
        }

        int result = 0;
        for (const auto& entry : numCount) {
            int num = entry.first;
            if (k == 0) {
                // When k == 0, we look for duplicates
                if (entry.second > 1) {
                    result++;
                }
            } else {
                // When k > 0, we look for the pair (num, num + k)
                if (numCount.find(num + k) != numCount.end()) {
                    result++;
                }
            }
        }
        
        return result;
    }
};

Time Complexity

The time complexity of the solution is (O(n)), where (n) is the number of elements in the array. This is because:

  1. Constructing the frequency counter takes (O(n)).
  2. Iterating through the hash map to count valid pairs also takes (O(n)) in the worst case.

The space complexity is also (O(n)) due to the storage required for the hash map.

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