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
ifx >= 0
. 
x
ifx < 0
.
Example 1:
Input: nums = [1,2,2,1], k = 1
Output: 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[valk];
}
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
andval + 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 += (valk >= 0 ? list[valk] : 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
Top comments (0)