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.
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
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
Salary: INR 17.6 LPA
Relocation/Signing Bonus: -
Stock bonus: 7 LPA vested over 4 years
Total comp (Salary + Bonus + Stock): 17.6 + 0 + 1.75 =INR 19.35 LPA
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.length
i != j
|nums[i] - nums[j]| == k
|val| denotes the absolute value of val.
Input: nums = [3,1,4,1,5], k = 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.
Input: nums = [1,2,3,4,5], k = 1
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
Explanation: There is one 0-diff pair in the array, (1, 1).
Input: nums = [1,2,4,4,3,3,0,9,2,3], k = 3
Input: nums = [-1,-2,-3], k = 1
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.
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.
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.
Other Data Structure Problems for Your Practice