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.
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.
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.