K-diff Pairs in an Array

Med

#0517Time: O(N^2), where N is the number of elements in `nums`. The two nested loops result in a quadratic time complexity as we compare every element with every other element.Space: O(P), where P is the number of unique pairs. In the worst-case scenario, P can be up to N, so the space complexity is O(N).2 companies

Patterns

Two Pointers

Algorithms

Binary Search Sorting

Data structures

Array Hash Table

Companies

tcs Capital One

Prompt

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
|nums[i] - nums[j]| == k

Notice that |val| denotes the absolute value of val.

Example 1:

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 2:

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 3:

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

Constraints:

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach iterates through all possible pairs of elements in the array and checks if their absolute difference is equal to k. To ensure that we only count unique pairs, a Set is used to store the pairs found in a canonical form.

Algorithm

Initialize an empty HashSet<String> called uniquePairs to store the unique pairs.
Iterate through the array with a pointer i from 0 to n-1.
Inside this loop, iterate with another pointer j from i+1 to n-1.
For each pair (nums[i], nums[j]), check if Math.abs(nums[i] - nums[j]) == k.
If the condition is true, form a canonical string representation of the pair, e.g., Math.min(nums[i], nums[j]) + "," + Math.max(nums[i], nums[j]), and add it to the uniquePairs set.
After the loops complete, return the size of uniquePairs.

Walkthrough

We can solve this problem by checking every possible pair of numbers in the array. We use two nested loops to generate these pairs.

For each pair (nums[i], nums[j]) where i < j, we calculate the absolute difference |nums[i] - nums[j]|.

If the difference equals k, we have found a k-diff pair. However, the problem asks for unique pairs. For example, in [1, 3, 1, 3] with k=2, the pair (1, 3) should be counted only once.

To handle this, we store the found pairs in a Set. To treat (a, b) and (b, a) as the same pair, we store them in a canonical order, for instance, (min(a, b), max(a, b)). A Set of Pair objects or a Set of String representations like "min_val,max_val" can be used.

The final result is the size of this set.

1import java.util.HashSet;2import java.util.Set;3 4class Solution {5    public int findPairs(int[] nums, int k) {6        if (k < 0) {7            return 0;8        }9        Set<String> uniquePairs = new HashSet<>();10        for (int i = 0; i < nums.length; i++) {11            for (int j = i + 1; j < nums.length; j++) {12                if (Math.abs(nums[i] - nums[j]) == k) {13                    int min = Math.min(nums[i], nums[j]);14                    int max = Math.max(nums[i], nums[j]);15                    uniquePairs.add(min + "," + max);16                }17            }18        }19        return uniquePairs.size();20    }21}

Complexity

Time

O(N^2), where N is the number of elements in `nums`. The two nested loops result in a quadratic time complexity as we compare every element with every other element.

Space

O(P), where P is the number of unique pairs. In the worst-case scenario, P can be up to N, so the space complexity is O(N).

Trade-offs

Pros

Simple to understand and implement.

Cons

Inefficient for large input arrays due to its O(N^2) time complexity, which will likely result in a 'Time Limit Exceeded' error on most platforms.

A more efficient approach involves sorting the array first. Once sorted, we can use a two-pointer technique to find the pairs in linear time. This method avoids redundant comparisons and handles duplicates effectively.

Algorithm

Sort the input array nums.
Initialize count = 0, left = 0, and right = 1.
Loop while right < nums.length.
If left == right or nums[right] - nums[left] < k, increment right.
Else if nums[right] - nums[left] > k, increment left.
Else (a pair is found):
- Increment count.
- Increment left.
- Skip any duplicates for the left pointer by advancing it while nums[left] == nums[left - 1].
- Move right to be at least left + 1.
Return count.

Walkthrough

This approach leverages the fact that if the array is sorted, we can search for pairs more efficiently.

First, we sort the input array nums.

We then use two pointers, left and right, initialized to 0 and 1 respectively.

We iterate while right is within the bounds of the array:

Calculate the difference diff = nums[right] - nums[left].
If diff == k, we've found a unique pair. We increment our count. To avoid counting duplicates, we then advance the left pointer past any subsequent identical elements.
If diff < k, the difference is too small. We need to increase it, so we move the right pointer to the right (right++).
If diff > k, the difference is too large. We need to decrease it, so we move the left pointer to the right (left++).

We must also handle the case where left and right pointers meet, by incrementing right to ensure left != right.

This two-pointer scan on the sorted array correctly identifies unique pairs without needing an extra set for the pairs themselves, as the duplicate handling is managed by advancing the pointers past identical elements.

1import java.util.Arrays;2 3class Solution {4    public int findPairs(int[] nums, int k) {5        Arrays.sort(nums);6        int count = 0;7        int left = 0;8        for (int right = 1; right < nums.length; right++) {9            // Skip duplicates for the right pointer10            if (right < nums.length - 1 && nums[right] == nums[right + 1]) {11                continue;12            }13            // Skip duplicates for the left pointer14            while (left < right && nums[left] == nums[left + 1]) {15                left++;16            }17            18            while (left < right && nums[right] - nums[left] > k) {19                left++;20            }21            22            if (left < right && nums[right] - nums[left] == k) {23                count++;24            }25        }26        return count;27    }28}

An alternative, perhaps simpler two-pointer implementation:

1import java.util.Arrays;2 3class Solution {4    public int findPairs(int[] nums, int k) {5        Arrays.sort(nums);6        int count = 0;7        int left = 0;8        int right = 1;9        while (left < nums.length && right < nums.length) {10            if (left == right || nums[right] - nums[left] < k) {11                right++;12            } else if (nums[right] - nums[left] > k) {13                left++;14            } else {15                count++;16                left++;17                while (left < nums.length && nums[left] == nums[left - 1]) {18                    left++;19                }20                right = Math.max(right + 1, left + 1);21            }22        }23        return count;24    }25}

Complexity

Time

O(N log N), dominated by the initial sorting of the array. The two-pointer scan takes O(N) time as each pointer traverses the array at most once.

Space

O(log N) or O(N), depending on the implementation of the sorting algorithm used. For example, in Java, `Arrays.sort()` for primitives uses a variant of Quicksort which has O(log N) space complexity on average.

Trade-offs

Pros

Significantly more efficient than the brute-force approach.
Handles duplicates elegantly after sorting.

Cons

The sorting step makes it slower than a hash-based approach.
The logic for handling duplicates and moving pointers can be tricky to get right.

The most optimal approach uses a hash map or a hash set to achieve linear time complexity. By storing elements and their frequencies (or just their presence), we can quickly check for the existence of the other element in a potential pair.

Algorithm

If k < 0, return 0.
If k == 0:
- Create a HashMap to store frequencies of numbers in nums.
- Iterate through the map's values. For each frequency greater than 1, increment a counter.
- Return the counter.
If k > 0:
- Create a HashSet and add all elements from nums to it to get unique numbers.
- Initialize a counter to 0.
- Iterate through each number num in the HashSet.
- Check if the set contains num + k. If it does, increment the counter.
- Return the counter.

Walkthrough

This approach handles the problem in O(N) time by using a hash-based data structure. The logic is slightly different for k=0 and k>0.

Case 1: k > 0

We want to find pairs (x, y) where y = x + k. To count unique pairs, we can first find all unique numbers in the input array. A HashSet is perfect for this.

Add all elements from nums into a HashSet to get rid of duplicates.
Initialize a count to 0.
Iterate through each number num in the hash set.
For each num, check if the set also contains num + k.
If it does, we have found a unique pair, so we increment count. By iterating through the unique numbers and only checking for num + k, we avoid double-counting.

Case 2: k = 0

We are looking for pairs (x, x), which means we need to find numbers that appear more than once in the array.

Use a HashMap to store the frequency of each number in nums.
Initialize a count to 0.
Iterate through the entries in the frequency map.
If a number's frequency is greater than 1, it can form a 0-diff pair. Increment count.

Finally, return the total count.

1import java.util.HashMap;2import java.util.Map;3import java.util.HashSet;4import java.util.Set;5 6class Solution {7    public int findPairs(int[] nums, int k) {8        if (k < 0) {9            return 0;10        }11        12        int count = 0;13        if (k == 0) {14            Map<Integer, Integer> freqMap = new HashMap<>();15            for (int num : nums) {16                freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);17            }18            for (int freq : freqMap.values()) {19                if (freq > 1) {20                    count++;21                }22            }23        } else { // k > 024            Set<Integer> uniqueNums = new HashSet<>();25            for (int num : nums) {26                uniqueNums.add(num);27            }28            for (int num : uniqueNums) {29                if (uniqueNums.contains(num + k)) {30                    count++;31                }32            }33        }34        return count;35    }36}

Complexity

Time

O(N), where N is the number of elements in `nums`. In both cases (`k=0` and `k>0`), we iterate through the array once to populate the hash map/set, and then iterate through the unique elements (at most N), with each operation being O(1) on average.

Space

O(N) in the worst case, where all elements are unique. The hash map or hash set needs to store up to N distinct elements.

Trade-offs

Pros

Most efficient time complexity at O(N).
The logic is straightforward and easy to reason about.

Cons

Requires extra space to store the hash map or hash set, which could be a concern for very large inputs with many unique elements.

Solutions

Solution

1class Solution {2public3  int findPairs(int[] nums, int k) {4    Set<Integer> vis = new HashSet<>();5    Set<Integer> ans = new HashSet<>();6    for (int v : nums) {7      if (vis.contains(v - k)) {8        ans.add(v - k);9      }10      if (vis.contains(v + k)) {11        ans.add(v);12      }13      vis.add(v);14    }15    return ans.size();16  }17}

1class Solution:2    def findPairs(self, nums: List[int], k: int) -> int: vis, ans = set(), set() for v in nums: if v - k in vis: ans . add(v - k) if v + k in vis: ans . add(v) vis . add(v) return len(ans)

1class Solution {2public:3  int findPairs(vector<int> &nums, int k) {4    unordered_set<int> vis;5    unordered_set<int> ans;6    for (int &v : nums) {7      if (vis.count(v - k))8        ans.insert(v - k);9      if (vis.count(v + k))10        ans.insert(v);11      vis.insert(v);12    }13    return ans.size();14  }15};

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  int findPairs(int[] nums, int k) {4    Set<Integer> vis = new HashSet<>();5    Set<Integer> ans = new HashSet<>();6    for (int v : nums) {7      if (vis.contains(v - k)) {8        ans.add(v - k);9      }10      if (vis.contains(v + k)) {11        ans.add(v);12      }13      vis.add(v);14    }15    return ans.size();16  }17}

1class Solution:2    def findPairs(self, nums: List[int], k: int) -> int: vis, ans = set(), set() for v in nums: if v - k in vis: ans . add(v - k) if v + k in vis: ans . add(v) vis . add(v) return len(ans)

1class Solution {2public:3  int findPairs(vector<int> &nums, int k) {4    unordered_set<int> vis;5    unordered_set<int> ans;6    for (int &v : nums) {7      if (vis.count(v - k))8        ans.insert(v - k);9      if (vis.count(v + k))10        ans.insert(v);11      vis.insert(v);12    }13    return ans.size();14  }15};

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.