Teaching Kids Programming – Count Number of Pairs With Absolute Difference K

Teaching Kids Programming: Videos on Data Structures and Algorithms

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

Explanation: The pairs with an absolute difference of 1 are:
– [1,2,2,1]
– [1,2,2,1]
– [1,2,2,1]
– [1,2,2,1]

Example 2:
Input: nums = [1,3], k = 3
Output: 0
Explanation: There are no pairs with an absolute difference of 3.

Example 3:
Input: nums = [3,2,1,5,4], k = 2
Output: 3
Explanation: The pairs with an absolute difference of 2 are:
– [3,2,1,5,4]
– [3,2,1,5,4]
– [3,2,1,5,4]

Constraints:
1 <= nums.length <= 200
1 <= nums[i] <= 100
1 <= k <= 99

Hints:
Can we check every possible pair?
Can we use a nested for loop to solve this problem?

Count Number of Pairs With Absolute Difference K via Bruteforce Algorithm

Bruteforcing the pairs of numbers take O(N^2) quadratic time. We then increment the answer/counter once the difference of pairs is K.

1
2
3
4
5
6
7
8
9

class Solution:
    def countKDifference(self, nums: List[int], k: int) -> int:
        ans = 0
        n = len(nums)
        for i in range(n):
            for j in range(i):
                if abs(nums[i] - nums[j]) == k:
                    ans += 1
        return ans

class Solution:
    def countKDifference(self, nums: List[int], k: int) -> int:
        ans = 0
        n = len(nums)
        for i in range(n):
            for j in range(i):
                if abs(nums[i] - nums[j]) == k:
                    ans += 1
        return ans

The space complexity is O(1) constant.

Count Number of Pairs With Absolute Difference K via Hash Table

We can count the numbers, and then use the multiplication rule to accumulate the answer quickly. The following algorithm takes O(N) time and O(N) space – based on a hash table. First pass is to count the numbers via Counter, and the second pass is to go through each unique numbers and multiply the corresponding frequency (could be i + k or i – k).

1
2
3
4
5
6
7

class Solution:
    def countKDifference(self, nums: List[int], k: int) -> int:
        c = Counter(nums)
        ans = 0
        for i in c:
            ans += c[i] * c[i + k]   # c[i - k] could also work
        return ans        

class Solution:
    def countKDifference(self, nums: List[int], k: int) -> int:
        c = Counter(nums)
        ans = 0
        for i in c:
            ans += c[i] * c[i + k]   # c[i - k] could also work
        return ans        

Here is another variant of using the hash table – we only perform one pass and update the counter.

1
2
3
4
5
6
7
8

class Solution:
    def countKDifference(self, nums: List[int], k: int) -> int:
        c = defaultdict(int)
        ans = 0
        for i in nums:
            ans += c[i - k] + c[i + k]
            c[i] += 1
        return ans

class Solution:
    def countKDifference(self, nums: List[int], k: int) -> int:
        c = defaultdict(int)
        ans = 0
        for i in nums:
            ans += c[i - k] + c[i + k]
            c[i] += 1
        return ans

–EOF (The Ultimate Computing & Technology Blog) —