# Count Number of Pairs With Absolute Difference K
**Difficulty:** EASY
[External](https://leetcode.com/problems/count-number-of-pairs-with-absolute-difference-k)
Canonical: https://scaleengineer.com/dsa/problems/count-number-of-pairs-with-absolute-difference-k
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table
**Companies:** [Expedia](https://scaleengineer.com/companies/expedia), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Oracle](https://scaleengineer.com/companies/oracle)
---
## Problem
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`

# Approaches
## Brute Force
The brute-force approach is the most straightforward way to solve the problem. It involves iterating through all possible pairs of elements in the array and checking if their absolute difference is equal to the given value `k`.
**Time:** O(N^2), where N is the number of elements in the `nums` array. The nested loops result in a quadratic number of comparisons. · **Space:** O(1). No extra data structures are used that scale with the input size. Only a few variables are needed for counting and iteration.
**Pros:** Very simple to understand and implement.; Uses constant extra space, making it memory-efficient.
**Cons:** Inefficient for large input arrays due to its quadratic time complexity.; May result in a 'Time Limit Exceeded' (TLE) error on platforms with strict time limits for larger inputs.
### Explanation
In this method, we use two nested loops to form every possible pair of distinct elements `(nums[i], nums[j])` such that the index `i` is less than `j`. For each pair, we compute the absolute difference. If this difference matches `k`, we increment a counter. While simple to conceive and implement, its performance degrades significantly as the size of the input array increases.

```java
class Solution {
    public int countKDifference(int[] nums, int k) {
        int count = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (Math.abs(nums[i] - nums[j]) == k) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter variable `count` to 0.
- Use a nested loop structure. The outer loop runs from `i = 0` to `n-1` and the inner loop runs from `j = i + 1` to `n-1`, where `n` is the length of the `nums` array. This ensures that each pair of indices `(i, j)` is considered only once and `i < j`.
- Inside the inner loop, calculate the absolute difference between `nums[i]` and `nums[j]`.
- If `Math.abs(nums[i] - nums[j])` is equal to `k`, increment the `count`.
- After the loops complete, return the final `count`.

## Using a Hash Map in a Single Pass
A more efficient approach uses a hash map to optimize the search for the second element of a pair. By storing the frequencies of numbers we've already seen, we can find a matching pair element in constant time on average.
**Time:** O(N), where N is the number of elements in `nums`. We iterate through the array once, and each hash map operation (get and put) takes O(1) time on average. · **Space:** O(U), where U is the number of unique elements in `nums`. In the worst-case scenario where all elements are unique, the space complexity is O(N).
**Pros:** Achieves linear time complexity, which is a significant improvement over the brute-force method.; It is a general solution that works well regardless of the range of numbers in the input array.
**Cons:** Requires extra space for the hash map, which can be up to O(N) in the worst case.
### Explanation
We can solve this problem in a single pass through the array. We use a hash map to keep track of the frequencies of the numbers we have visited so far. For each element `num` in the array, we check if `num - k` or `num + k` exists in our hash map. If they do, it means we have found one or more pairs. The number of such pairs is equal to the frequency of `num - k` and `num + k` stored in the map. We add these frequencies to our total count. After processing the checks for the current `num`, we update its own frequency in the map. This ensures that for any pair `(nums[i], nums[j])` with `i < j`, the pair is counted exactly once when we are processing `nums[j]`.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int countKDifference(int[] nums, int k) {
        Map<Integer, Integer> freqMap = new HashMap<>();
        int count = 0;
        for (int num : nums) {
            // Check for pairs where the other element is smaller or larger
            count += freqMap.getOrDefault(num - k, 0);
            count += freqMap.getOrDefault(num + k, 0);
            
            // Update the frequency of the current number for subsequent elements
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Create a `HashMap` named `freqMap` to store the frequency of each number encountered.
- Iterate through each number `num` in the `nums` array.
- For each `num`, check for the existence of its potential pair-mates: `num - k` and `num + k`.
- Add the frequency of `num - k` (if it exists in `freqMap`) to `count`.
- Add the frequency of `num + k` (if it exists in `freqMap`) to `count`.
- After checking for pairs, update the frequency of the current `num` in `freqMap`. Increment its count if it's already present, or add it with a count of 1 if it's not.
- Return `count` after iterating through all the numbers.

## Optimized Counting with a Frequency Array
Leveraging the problem's constraints that `nums[i]` is between 1 and 100, we can use a simple fixed-size array as a frequency map instead of a hash map. This approach is highly efficient in both time and space.
**Time:** O(N + M), where N is the length of `nums` and M is the range of values (100). This is because we iterate through `nums` once (O(N)) and then through the frequency array (O(M)). As M is constant, this simplifies to O(N). · **Space:** O(M), where M is the maximum possible value of an element in `nums` (100 in this case). Since M is a constant, the space complexity is O(1).
**Pros:** Extremely fast with a time complexity of O(N + M), which is linear.; Very memory-efficient with constant space complexity, as the frequency array size is fixed.
**Cons:** This solution is not general and relies heavily on the specific constraints of the problem (i.e., the small and fixed range of input values).; It would be inefficient if the range of numbers were very large.
### Explanation
This method consists of two main parts. First, we determine the frequency of each number in the input array. Since the numbers are limited to the range [1, 100], we can use a simple array of size 101 for this purpose, where `freq[x]` stores the number of occurrences of `x`. We populate this frequency array by iterating through `nums`.

Second, we calculate the pairs. We can iterate through our frequency array from `i = 1` to `100`. For each number `i`, we are looking for a pair `j` such that `j - i = k`, which means `j = i + k`. The number of such pairs is simply the product of the frequencies of `i` and `i + k`. By iterating `i` from 1 upwards and only considering `i + k`, we avoid double-counting. The total count is the sum of these products.

```java
class Solution {
    public int countKDifference(int[] nums, int k) {
        // Constraints: 1 <= nums[i] <= 100, 1 <= k <= 99
        int[] freq = new int[101];
        for (int num : nums) {
            freq[num]++;
        }
        
        int count = 0;
        // Iterate through possible smaller numbers of a pair
        for (int i = 1; i <= 100 - k; i++) {
            // The other number in the pair is i + k
            if (freq[i + k] > 0) {
                count += freq[i] * freq[i + k];
            }
        }
        
        return count;
    }
}
```
### Algorithm
- Since `1 <= nums[i] <= 100`, create an integer array `freq` of size 101, initialized to all zeros. This will act as a frequency map.
- Iterate through the input array `nums` once to populate the `freq` array. For each `num` in `nums`, increment `freq[num]`.
- Initialize a counter `count` to 0.
- Iterate with a variable `i` from 1 up to `100 - k`.
- For each `i`, its corresponding pair would be `i + k`. The number of pairs formed between `i` and `i + k` is the product of their frequencies: `freq[i] * freq[i + k]`.
- Add this product to the `count`.
- After the loop finishes, return the total `count`.

# Solutions
### Java

```java
countDownLatch1 = new CountDownLatch ( 1 ); countDownLatch2 = new CountDownLatch ( 1 ); countDownLatch1 . await (); countDownLatch2 . countDown ();
```

### Python

```python
>>> nums = [ 4 , 5 , 5 , 6 ] >>> mid = ( len ( nums ) - 1 ) // 2 >>> mid 1 >>> nums [ mid :: - 1 ] [ 5 , 4 ] >>> nums [: mid : - 1 ] [ 6 , 5 ] >>> nums [:: 2 ], nums [ 1 :: 2 ] = nums [ mid :: - 1 ], nums [: mid : - 1 ] >>> nums [ 5 , 6 , 4 , 5 ] >>> nums [ mid :: 1 ] [ 5 , 5 , 6 ] >>> nums [ mid :] [ 5 , 5 , 6 ] >>> nums [: mid : 1 ] [ 4 ] >>> nums [: mid ] [ 4 ]
```