2006. Count Number of Pairs With Absolute Difference K

Description

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

Solutions

Solution 1: Brute Force Enumeration

Thinking

With \(n \le 200\), enumerating all \(i<j\) and testing \(|nums[i]-nums[j]|=k\) is about \(2 \times 10^4\) pairs, which fits. Values and \(k\) are small, so no extra structure is required.

The double loop matches the definition directly.

We notice that the length of the array \(nums\) does not exceed \(200\), so we can enumerate all pairs \((i, j)\), where \(i < j\), and check if \(|nums[i] - nums[j]|\) equals \(k\). If it does, we increment the answer by one.

Finally, we return the answer.

The time complexity is \(O(n^2)\), and the space complexity is \(O(1)\). Here, \(n\) is the length of the array \(nums\).

Python3JavaC++GoTypeScriptRust

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

class Solution {
    public int countKDifference(int[] nums, int k) {
        int ans = 0;
        for (int i = 0, n = nums.length; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (Math.abs(nums[i] - nums[j]) == k) {
                    ++ans;
                }
            }
        }
        return ans;
    }
}

class Solution {
public:
    int countKDifference(vector<int>& nums, int k) {
        int n = nums.size();
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                ans += abs(nums[i] - nums[j]) == k;
            }
        }
        return ans;
    }
};

func countKDifference(nums []int, k int) int {
    n := len(nums)
    ans := 0
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            if abs(nums[i]-nums[j]) == k {
                ans++
            }
        }
    }
    return ans
}

func abs(x int) int {
    if x > 0 {
        return x
    }
    return -x
}

function countKDifference(nums: number[], k: number): number {
    let ans = 0;
    let cnt = new Map();
    for (let num of nums) {
        ans += (cnt.get(num - k) || 0) + (cnt.get(num + k) || 0);
        cnt.set(num, (cnt.get(num) || 0) + 1);
    }
    return ans;
}

impl Solution {
    pub fn count_k_difference(nums: Vec<i32>, k: i32) -> i32 {
        let mut res = 0;
        let n = nums.len();
        for i in 0..n - 1 {
            for j in i..n {
                if (nums[i] - nums[j]).abs() == k {
                    res += 1;
                }
            }
        }
        res
    }
}

Solution 2: Hash Table or Array

Thinking

Solution 1 visits every pair. We only need the count of difference \(k\): for current \(x\), earlier \(x-k\) and \(x+k\) pair with it.

A running counter adds those hits, then records \(x\), giving a linear one-pass tally.

We can use a hash table or array to record the occurrence count of each number in the array \(nums\). Then, we enumerate each number \(x\) in the array \(nums\), and check if \(x + k\) and \(x - k\) are in the array \(nums\). If they are, we increment the answer by the sum of the occurrence counts of \(x + k\) and \(x - k\).

Finally, we return the answer.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of the array \(nums\).

Python3JavaC++GoRust

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

class Solution {
    public int countKDifference(int[] nums, int k) {
        int ans = 0;
        int[] cnt = new int[110];
        for (int num : nums) {
            if (num >= k) {
                ans += cnt[num - k];
            }
            if (num + k <= 100) {
                ans += cnt[num + k];
            }
            ++cnt[num];
        }
        return ans;
    }
}

class Solution {
public:
    int countKDifference(vector<int>& nums, int k) {
        int ans = 0;
        int cnt[110]{};
        for (int num : nums) {
            if (num >= k) {
                ans += cnt[num - k];
            }
            if (num + k <= 100) {
                ans += cnt[num + k];
            }
            ++cnt[num];
        }
        return ans;
    }
};

func countKDifference(nums []int, k int) (ans int) {
    cnt := [110]int{}
    for _, num := range nums {
        if num >= k {
            ans += cnt[num-k]
        }
        if num+k <= 100 {
            ans += cnt[num+k]
        }
        cnt[num]++
    }
    return
}

impl Solution {
    pub fn count_k_difference(nums: Vec<i32>, k: i32) -> i32 {
        let mut arr = [0; 101];
        let mut res = 0;
        for num in nums {
            if num - k >= 1 {
                res += arr[(num - k) as usize];
            }
            if num + k <= 100 {
                res += arr[(num + k) as usize];
            }
            arr[num as usize] += 1;
        }
        res
    }
}