- Published on

# Count Number of Pairs With Absolute Difference K.

- Authors
- Name
- Pankaj Tanwar
- @the2ndfloorguy

Bonjour!

Thanks for sticking along, it's day 15 of my coding diary. Well, I started this journey to discipline my self and I feel, now I am literally enjoying it. Let's jump to the problem statement for today.

TLDR;

- Never settle down by just seeing green tick with brute force approach. Think harder to reach the optimized one. (I found 3 approaches for the problem)
- Easy problems might have interesting hidden challenges

**Problem of the day** - Count Number of Pairs With Absolute Difference K

**Tag** - Easy

Given an integer array `nums`

and an integer `k`

, return *the number of pairs* `(i, j)`

*where* `i < j`

*such that* `|nums[i] - nums[j]| == k`

.

The value of `|x|`

is defined as:

`x`

if`x >= 0`

.`-x`

if`x < 0`

.

**Example 1:**

Input:nums = [1,2,2,1], k = 1Output:4

Just after reading the problem statement carefully, like any other dev, a brute force, O(n2), the slowest approach came to my mind and I just started typing without wasting a second.

`class Solution {public: int countKDifference(vector<int>& nums, int k) { int res = 0; for(int i=0;i<nums.size();i++) { for(int j=i+1;j<nums.size();j++) { if(abs(nums[i]- nums[j]) == k) res++; } } return res; }};`

As expected, the worst approach. It took 39ms, faster than 7%, Arghhhh. I knew it.

I again read the problem statement. A quick thought came to my mind, why not store count for each value and check count of `val + k`

and `val - k`

.

`class Solution {public: int countKDifference(vector<int>& nums, int k) { map<int,int> list; int res = 0; for(auto val: nums) list[val]++; for(auto val: nums) { list[val]--; res += list[val+k] + list[val-k]; } return res; }};`

**Approach** -

- Store count of each value
- Iterate over the
`nums`

array - For each element, reduce the count for the current value first, and check the count of
`val - k`

and`val + k`

- return the final value, that's the answer

I hit submit in the excitement of O(n) approach, BUT leetcode said, Ummm, it's a good try but still slower than 60% submission, think harder. WTH, I thought I cracked it.

I kept on digging more. I again read the problem statement, no luck! Suddenly, I looked at the constraints. It was a light bulb moment.....

**Constraints:**

`1 <= nums.length <= 200`

`1 <= nums[i] <= 100`

`1 <= k <= 99`

Let's remove the sluggish hashmap and use an array of length 200.

`class Solution {public: int countKDifference(vector<int>& nums, int k) { int list[201] = {0}; int res = 0; for(auto val: nums) { res += (val-k >= 0 ? list[val-k] : 0) + list[val+k]; list[val]++; } return res; }}`

Hit submit, and boom! It's 9ms, faster than 90% of solutions. Oh man, that was fun. I am gradually recognizing the patterns.

You might like previous editions of my coding diary