Count Number of Pairs With Absolute Difference K

LeetCode 2116 | Difficulty: Easy

Easy

Problem Description

Given an integer array nums and an integer k, return the number of pairs (i, j) where i = 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`

Topics: Array, Hash Table, Counting

---

Approach

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

---

Solutions

Solution 1: C# (Best: 119 ms)

Metric	Value
Runtime	119 ms
Memory	38.8 MB
Date	2022-02-07

Solution

public class Solution {
    public int CountKDifference(int[] nums, int k)
{
    Dictionary<int, int> d = new Dictionary<int, int>();
    int count = 0;
    foreach (var num in nums)
    {
        if (d.ContainsKey(num))
        {
            d[num]++;
        }
        else d.Add(num, 1);
        if (d.ContainsKey(num - k)) count += d[num - k];
        if (d.ContainsKey(num + k)) count += d[num + k];        
    }
    return count;
}
}

📜 1 more C# submission(s)

Submission (2022-02-07) — 233 ms, 38.3 MB

public class Solution {
    public int CountKDifference(int[] nums, int k)
{
    Dictionary<int, int> d = new Dictionary<int, int>();
    int count = 0;
    foreach (var num in nums)
    {
        if (d.ContainsKey(num))
        {
            if (k == 0)
                count += d[num];
            d[num]++;
        }
        else d.Add(num, 1);
            if (k>0 && d.ContainsKey(num - k)) count += d[num - k];
            if (k>0 && d.ContainsKey(num + k)) count += d[num + k];
            
        
    }
    return count;
}
}

---

Complexity Analysis

Approach	Time	Space
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Hash map gives O(1) lookup — think about what to use as key vs value.
• LeetCode provides 2 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Can we check every possible pair?

Hint 2: Can we use a nested for loop to solve this problem?