In this series, I am going to solve Leetcode medium problems live with my friend, which you can see on our youtube channel, Today we will do Problem 532. K-diff Pairs in an Array.
A little bit about me, I have offers from Uber India and Amazon India in the past, and I am currently working for Booking.com in Amsterdam.
Youtube Discussion
Please comment here or on youtube, if you have any doubts.
0:00 — Intro
0:50 — Max Area of Island (Problem statement & Algorithm)
3:55 — Python code
14:50 — Debugging the code
19:55 — K-diff pairs in an array
42:40 — Explanation of correct algorithm
49:30 — Python code
Motivation to Learn Algorithms
I have worked in India as a software developer for 4 years. I started learning algorithms and data structure from my 3rd year in college as I was from an Electronics background. Here is my salary progression over the years, (all in INR, Lakh per year)
2016: placement in Flipkart from college, IIT KGP(18 lakh base + 2 lakh bonus = 20 lakh). But the offer was delayed by 6 months, as Flipkart was going through some trouble, so I joined Samsung.
2016: Samsung Noida(off campus ) (14 lakh base + 5 lakh joining bonus = 19 lakh). They pay to IITians 19 lakh but other colleges 9-14 lakh for the same work, which is bogus.
2017: Oyorooms (17 lakh fixed, no bonus, no stocks). I took a pay cut as I was not learning anything in Samsung, so joined Oyo.
2019: Sharechat (26 lakh fixed + 2.6lakh bonus + stock options) I joined Sharechat in Bangalore, as SDE1
2020: Offer from Amazon ( 26.5 lakh base + 18.5 lakh joining bonus= 43 lakh) in SDE2 role. They offer stocks but it is vested only 5 percent in the first year, so I ignored it.
Offer from Uber (33 lakh base + 15 lakh stock options per year (96000 USD over 4 years)+ 5 lakh joining bonus = 55 lakh per year) in SDE2 role. I think that is the top salary, you can get 3.5–4 years experience in India, but I might be wrong.
A lot of startups and established companies in India pay over 35 lakh per year for the top talent in programming, for just over 4 years of experience, like Dunzo, Dream11, Rubric, etc, check
Even if you are not from a good college, you can still land awesome jobs, for let's take this example
Education: B.Tech in CS from Tier 3 college
Years of Experience: 2
Prior Experience: Java Developer at Startup
current CTC: INR 3.2 LPA+1 LPA(Bonus)
Date of the Offer:Dec 2020
Company: Swiggy
Title/Level:SDE -1
Location: Bangalore
Salary: INR 17.6 LPA
Relocation/Signing Bonus: -
Stock bonus: 7 LPA vested over 4 years
Bonus: -
Total comp (Salary + Bonus + Stock): 17.6 + 0 + 1.75 =INR 19.35 LPA
Benefits: -
Other details: Not even a single word from me after this digits are spoken by the recruiter.
Has a 6 months career gap even at the time of offer.
I rejected both offers and ended up joining Booking.com as I wanted to explore Europe. I can’t disclose my current salary.
I got so many offers because I practiced a lot of data structure and algorithm problems. I solved over 410 questions in Leetcode.
Nil Masdhab - Leetcode Profile
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 are true:
0 <= i, j < nums.lengthi != 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).
Example 4:
Input: nums = [1,2,4,4,3,3,0,9,2,3], k = 3
Output: 2
Example 5:
Input: nums = [-1,-2,-3], k = 1
Output: 2
Solution :
To solve this problem, we will have to use a dictionary (HashMap in Java). In this problem, we need to count the number of unique k-diff pairs in the array. k-diff means that the absolute difference between the two elements should be k.
At first, we store the elements as keys and it’s an index of occurrence as a list in a dictionary. So now we can find an element whose absolute difference is k from this number. So we will check if element+k is present in the dictionary if it is present and we add this pair to the ans dictionary. We do the same as element-k.
But there is a catch if k=0 then we have to check the total occurrence of each element. If it is greater than 1 then we add this to the ans dictionary.
At last, we return the length of the dictionary which is our answer.
| class Solution(object): | |
| def findPairs(self, nums, k): | |
| dic = {} | |
| #We create an iterator, i is the index in the array and element is the integer in that array. | |
| #Here we will create dictionary. | |
| # [3,1,4,1,5] , k=2 | |
| # So for this input we will create a dictionary | |
| # 3 ->[0] , 1 -> [1,3] , 4-> [2] , 5-> [4] | |
| # nums = [1,3,1,5,4], k = 0 | |
| # 1 -> [0,2] , 3 -> [1] , 5 -> [3] , 4-> [4] | |
| # As k=0; this is a special case, so we will check occurance of a no . | |
| # As 1 appears twice, our output will be 1. | |
| for i, element in enumerate(nums): | |
| if element in dic: | |
| dic[element].append(i) | |
| else: | |
| dic[element] = [i] | |
| #The answer dictionary contains the possible pairs for this problem. | |
| ans = {} | |
| #We run a loop for each element in the dictionary. | |
| for element in dic: | |
| #k==0 is a special case. So if we have multiple occurance a no , then we can consider one pair for it. | |
| if k == 0: | |
| if len(dic[element]) > 1: | |
| ans[(element, element)] = True | |
| else: | |
| #As the k-diff is taken as absolute , we have to check for both element+k and element-k in the dictionary. | |
| #If it is present we will add them into the ans dictionary. | |
| if element + k in dic: | |
| ans[(element, element+k)] = True | |
| if element -k in dic: | |
| ans[(element-k, element)] = True | |
| #We just have to return the size of the ans dictionary | |
| return len(ans) | |
We came up with a better approach in java to solve this problem later. We can reduce it’s overall used space by making a HashMap with Element as key and a counter as value. In this way, we first store the frequency of all elements of the array in a hashMap.
After that, we iterate through all the keys of the hashMap(basically this is iterating through the array elements but without repetition). We search if (element+k) is present in the hashMap and if it is present then we increment the ans variable.
To handle k=0 case, we check whether that element occurs more than once, if so then we increment the ans variable.
Here is optimized java code for the problem.
| public class LC532 { | |
| public int findPairs(int[] nums, int k) { | |
| // Dry Run | |
| // nums = [3,1,4,1,5], k = 2 | |
| // <3->1>, <1->2> , <4->1>, <5->1> ; Here <Array Element -> Occurance of that element> | |
| // As k=2 ; we have 1+2 = 3 and 3+2 = 5 ; which makes (1,3) and (3,5) k-diff pair; output will be 2 | |
| // nums = [1,3,1,5,4], k = 0 | |
| // <1->2>, <3->1>,<5->1>,<4->1> ; | |
| // As k=0; this is a special case, so we will check occurance of a no . | |
| // As 1 appears twice, our output will be 1. | |
| //Absolute Differnce can not negative | |
| if(k<0) | |
| return 0; | |
| //We are having a HashMap which takes <Element,Counter> as a pair. | |
| //The first Integer keeps the array element and second Integer keeps the counter for that element. | |
| HashMap<Integer,Integer> hashMap = new HashMap<>(); | |
| for(int i=0;i<nums.length;i++){ | |
| int curr = nums[i]; | |
| if(hashMap.containsKey(curr)) | |
| hashMap.put(curr,hashMap.get(curr)+1); | |
| else | |
| hashMap.put(curr,1); | |
| } | |
| //Now we have the frequency of each element stored in the hashMap. | |
| int ans = 0; | |
| //We run a loop for each key in the hashMap. | |
| for(int i:hashMap.keySet()){ | |
| //So here is the integer which we have to search for in the hashMap | |
| int remainder = i+k; | |
| //k==0 is a special case. So if we have multiple occurance a no , | |
| // then we can consider one pair for it. | |
| if(k==0){ | |
| if(hashMap.get(i)>=2){ | |
| ans++; | |
| } | |
| } | |
| else{ | |
| //If remainder is present in the hashMap, increment ans variable. | |
| if(hashMap.containsKey(remainder)){ | |
| ans++; | |
| } | |
| } | |
| } | |
| return ans; | |
| } | |
| } |
Time Complexity: O(n), n is the size of the array
Space Complexity: O(n), n is the size of the array
All the code can be found in the following GitHub repo.
https://github.com/webtutsplus/LeetCode/tree/main/src/LC532_kdiffPairs
Other Data Structure Problems for Your Practice
Medium
Top comments (2)
Thanks for this this. Helpful.
you are welcome, follow me on Twitter to read my latest posts in the medium for FREE.