Challenge #15 - Count Number of Pairs With Absolute Difference K

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 = 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[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

• Day #14 - Minimum Number of Operations to Move All Balls to Each Box.
• Day #13 - Number Of Rectangles That Can Form The Largest Square.
• Day #12 - Unique Morse Code Words.
• Day #11 - Count the Number of Consistent Strings.
• Day #10 - Find Greatest Common Divisor of Array.