Leetcode 532. K-diff Pairs in an Array
Problem
Given an array of integers and an integer k
, we need to find the count of unique k-diff
pairs in the array. A k-diff
pair is defined as a pair of integers (i, j)
where i
and j
are both numbers in the array and their absolute difference is k
.
Example:
For array [3,1,4,1,5]
and k = 2
, the output will be 2
because there are two 2-diff
pairs in the array, (1, 3)
and (3, 5)
. Though we have two 1
s in the input, but, we only return a count of unique pairs. So, 1
will only be counted once.
The pairs (i, j)
and (j, i)
are counted as the same pair. The lengths of the arrays will not exceed 10,000
and all the integers in the array input will be in the range of -1e7 to 1e7
.
Approach
The problem can be solved efficently by using the sliding window
and two pointers
concepts. But, in our solution we're using a Hash Map
(Dictionary in Python and Map in JavaScript). The steps are as follows -
- In the first loop, we fill our map where the pairs are (
nums[i]
,i
), i.e.,(array element, its index)
. - In the second loop, we look for a pair whose difference equals to
k
. If found, we increase our answer by1
and remove the found pair from the map to avoid double counting.
Walkthrough
Let's use the given example - In [3, 1, 4, 1, 5]
with k = 2
, the 2-diff
pairs are (1, 3)
and (3, 5)
. So, the output will be 2
.
Python Solution
1 2python 3class Solution: 4 def findPairs(self, nums, k): 5 ans = 0 6 numToDict = {} 7 for i in range(len(nums)): 8 numToDict[nums[i]] = i 9 for i in range(len(nums)): 10 target = nums[i] + k 11 if target in numToDict and numToDict[target] != i: 12 ans += 1 13 numToDict.pop(target) 14 return ans
Java Solution
1 2java 3public class Solution { 4 public int findPairs(int[] nums, int k) { 5 int ans = 0; 6 HashMap<Integer, Integer> numToIndex = new HashMap<>(); 7 for (int i = 0; i < nums.length; ++i) 8 numToIndex.put(nums[i], i); 9 for (int i = 0; i < nums.length; ++i) { 10 int target = nums[i] + k; 11 if (numToIndex.containsKey(target) && numToIndex.get(target) != i) { 12 ans++; 13 numToIndex.remove(target); 14 } 15 } 16 return ans; 17 } 18}
JavaScript Solution
1 2javascript 3class Solution { 4 findPairs(nums, k) { 5 let ans = 0; 6 let numToIndex = {}; 7 for (let i = 0; i < nums.length; i++) 8 numToIndex[nums[i]] = i; 9 for (let i = 0; i < nums.length; i++) { 10 let target = nums[i] + k; 11 if (numToIndex.hasOwnProperty(target) && numToIndex[target] != i) { 12 ans++; 13 delete numToIndex[target]; 14 } 15 } 16 return ans; 17 } 18}
C++ Solution
1
2cpp
3class Solution {
4public:
5 int findPairs(vector<int>& nums, int k) {
6 int ans = 0;
7 unordered_map<int, int> numToIndex;
8 for (int i = 0; i < nums.size(); ++i)
9 numToIndex[nums[i]] = i;
10 for (int i = 0; i < nums.size(); ++i) {
11 int target = nums[i] + k;
12 if (numToIndex.find(target) != numToIndex.end() && numToIndex[target] != i) {
13 ans++;
14 numToIndex.erase(target);
15 }
16 }
17 return ans;
18 }
19};
C# Solution
1 2csharp 3public class Solution { 4 public int FindPairs(int[] nums, int k) { 5 int ans = 0; 6 Dictionary<int, int> numToIndex = new Dictionary<int, int>(); 7 for (int i = 0; i < nums.Length; ++i) 8 numToIndex[nums[i]] = i; 9 for (int i = 0; i < nums.Length; ++i) { 10 int target = nums[i] + k; 11 if (numToIndex.ContainsKey(target) && numToIndex[target] != i) { 12 ans++; 13 numToIndex.Remove(target); 14 } 15 } 16 return ans; 17 } 18}
In above solutions, we store element and its index in our hash map. We then iterate over the array to find element which have a difference of k
from current element. If we find such pair, we remove it from map to avoid double count. We return count as our answer.# Time Complexity
The time complexity of these solutions is O(n) because we are looping through the array twice. The first pass is to populate the dictionary/map with all the numbers in the array and their corresponding indices. The second pass is to check whether each number has a corresponding pair that is k
different, so each loop runs in linear time. Here, 'n' refers to the length of the array
The space complexity is also O(n) because we're storing every number and its index in the dictionary or map, which can reach up to 'n' elements in size.
Solution Test Cases for Python
1 2python 3test = Solution() 4print(test.findPairs([3,1,4,1,5], 2)) # return 2 5print(test.findPairs([1,2,3,4,5], 1)) # return 4 6print(test.findPairs([1,3,1,5,4], 0)) # return 1 7print(test.findPairs([], 1)) # return 0 8print(test.findPairs([1,1,1,1,1], 0)) # return 1
Solution Test Cases for Java
1
2java
3public static void main(String[] args) {
4 Solution test = new Solution();
5 System.out.println(test.findPairs(new int[] {3,1,4,1,5}, 2)); // returns 2
6 System.out.println(test.findPairs(new int[] {1,2,3,4,5}, 1)); // returns 4
7 System.out.println(test.findPairs(new int[] {1,3,1,5,4}, 0)); // returns 1
8 System.out.println(test.findPairs(new int[] {}, 1)); // returns 0
9 System.out.println(test.findPairs(new int[] {1,1,1,1,1}, 0)); // returns 1
10}
Solution Test Cases for JavaScript
1 2javascript 3let test = new Solution(); 4console.log(test.findPairs([3,1,4,1,5], 2)); // returns 2 5console.log(test.findPairs([1,2,3,4,5], 1)); // returns 4 6console.log(test.findPairs([1,3,1,5,4], 0)); // returns 1 7console.log(test.findPairs([], 1)); // returns 0 8console.log(test.findPairs([1,1,1,1,1], 0)); // returns 1
Solution Test Cases for C++
1 2cpp 3int main() { 4 Solution test; 5 vector<int> v1 = {3,1,4,1,5}; 6 cout << test.findPairs(v1, 2) << endl; // returns 2 7 vector<int> v2 = {1,2,3,4,5}; 8 cout << test.findPairs(v2, 1) << endl; // returns 4 9 vector<int> v3 = {1,3,1,5,4}; 10 cout << test.findPairs(v3, 0) << endl; // returns 1 11 vector<int> v4 = {}; 12 cout << test.findPairs(v4, 1) << endl; // returns 0 13 vector<int> v5 = {1,1,1,1,1}; 14 cout << test.findPairs(v5, 0) << endl; // returns 1 15 return 0; 16}
Solution Test Cases for C#
1 2csharp 3public static void Main() { 4 Solution test = new Solution(); 5 Console.WriteLine(test.FindPairs(new int[] {3,1,4,1,5}, 2)); // returns 2 6 Console.WriteLine(test.FindPairs(new int[] {1,2,3,4,5}, 1)); // returns 4 7 Console.WriteLine(test.FindPairs(new int[] {1,3,1,5,4}, 0)); // returns 1 8 Console.WriteLine(test.FindPairs(new int[] {}, 1)); // returns 0 9 Console.WriteLine(test.FindPairs(new int[] {1,1,1,1,1}, 0)); // returns 1 10}
By running these test cases, you can be confident that the given solutions are correct.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.