Challenge #15 - Count Number of Pairs With Absolute Difference K
Tags: javascript, programming, codenewbie, leetcode
Published: 2021-10-03 06:36:40

Bonjour!

Thanks for sticking along, it's day 15 of [my coding diary](https://www.pankajtanwar.in/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

<hr/>

**Problem of the day** - [Count Number of Pairs With Absolute Difference K](https://leetcode.com/problems/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 = 1
> **Output:** 4

<hr/>

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.

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

<hr/>

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

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

<hr/>

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. 

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

<hr/>

You might like previous editions of [my coding diary](https://www.pankajtanwar.in/coding-diary)

- [Day #14 - Minimum Number of Operations to Move All Balls to Each Box.](https://www.pankajtanwar.in/code/minimum-number-of-operations-to-move-all-balls-to-each-box/)
- [Day #13 - Number Of Rectangles That Can Form The Largest Square.](https://www.pankajtanwar.in/code/number-of-rectangles-that-can-form-the-largest-square/)
- [Day #12 - Unique Morse Code Words.](https://www.pankajtanwar.in/code/unique-morse-code-words/)
- [Day #11 - Count the Number of Consistent Strings.](https://www.pankajtanwar.in/code/count-the-number-of-consistent-strings/)
- [Day #10 - Find Greatest Common Divisor of Array.](https://www.pankajtanwar.in/code/find-greatest-common-divisor-of-array/)