Solve Leetcode Problems and Get Offers From Your Dream Companies | K-diff Pairs in an Array
Tags: algorithms, career
Published: 2021-01-20 14:07:07

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.
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/pn6skybbr2rh76bjut1f.jpg)
## Youtube Discussion

Please comment here or on youtube, if you have any doubts.
{% youtube iO9Y8zDqwaQ %}
* [0:00](https://www.youtube.com/watch?v=iO9Y8zDqwaQ&t=0s) — Intro

* [0:50](https://www.youtube.com/watch?v=iO9Y8zDqwaQ&t=50s) — Max Area of Island (Problem statement & Algorithm)

* [3:55](https://www.youtube.com/watch?v=iO9Y8zDqwaQ&t=235s) — Python code

* [14:50](https://www.youtube.com/watch?v=iO9Y8zDqwaQ&t=890s) — Debugging the code

* [19:55](https://www.youtube.com/watch?v=iO9Y8zDqwaQ&t=2560s) — K-diff pairs in an array

* [42:40](https://www.youtube.com/watch?v=iO9Y8zDqwaQ&t=2560s) — Explanation of correct algorithm

* [49:30](https://www.youtube.com/watch?v=iO9Y8zDqwaQ&t=2970s) — 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](https://leetcode.com/nilmadhab/)

**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`

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)](https://www.java67.com/2013/02/10-examples-of-hashmap-in-java-programming-tutorial.html). 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.
{% gist https://gist.github.com/sksaikia/64ae1a5a6d705faf41080180166439ec.js %}
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](https://www.java67.com/2017/08/top-10-java-hashmap-interview-questions.html) 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](http://javarevisited.blogspot.sg/2016/08/how-to-iterate-through-ConcurrentHashMap-print-all-keys-values-java.html#axzz4pdz6fpLN)(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.
{% gist https://gist.github.com/sksaikia/16a6cf81e642fab30b43467f145b6904.js %}

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 https://medium.com/javarevisited/20-array-coding-problems-and-questions-from-programming-interviews-869b475b9121 %}

{% medium https://medium.com/javarevisited/top-21-string-programming-interview-questions-for-beginners-and-experienced-developers-56037048de45 %}