Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2006.html

2006. Count Number of Pairs With Absolute Difference K (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
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

Similar Questions:

Solution 1. Brute Force

// Time: O(N^2)
// Space: O(1)
class Solution {
public:
    int countKDifference(vector<int>& A, int k) {
        int N = A.size(), ans = 0;
        for (int i = 0; i < N; ++i) {
            for (int j = i + 1; j < N; ++j) {
                ans += abs(A[i] - A[j]) == k;
            }
        }
        return ans;
    }
};

Solution 2. Sliding Window

After sorting the array A, we can use sliding window to count the number of elements == A[i] + k so that we just traverse A once.

// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    int countKDifference(vector<int>& A, int k) {
        int N = A.size(), ans = 0, j = 0;
        sort(begin(A), end(A));
        for (int i = 0; i < N; ) {
            int n = A[i], cnt = 0;
            while (i < N && A[i] == n) ++i, ++cnt;
            while (j < N && A[j] < n + k) ++j;
            int start = j;
            while (j < N && A[j] == n + k) ++j;
            ans += (j - start) * cnt;
        }
        return ans;
    }
};

Solution 3. Frequency Map

// Time: O(N)
// Space: O(C) where `C` is the range of numbers in `A`.
class Solution {
public:
    int countKDifference(vector<int>& A, int k) {
        int N = A.size(), ans = 0, cnt[101] = {};
        for (int n : A) {
            ans += (n + k <= 100 ? cnt[n + k] : 0) + (n - k >= 1 ? cnt[n - k] : 0);
            cnt[n]++;
        }
        return ans;
    }
};

All Problems

All Solutions