Count Number of Pairs With Absolute Difference K

Easy
755.

Count Number of Pairs With Absolute Difference K

Count Number of Pairs With Absolute Difference K is an easy coding problem on arrays, hash table and counting, asked in TCS, Wipro and Zoho interviews.

Count the pairs of indices (i, j) with i < j and |nums[i] - nums[j]| == k.

Example 1

Input
nums = [1,2,2,1], k = 1
Output
4
Explanation
Each 1 pairs with each 2.

Example 2

Input
nums = [1,3], k = 3
Output
0

Example 3

Input
nums = [3,2,1,5,4], k = 2
Output
3
Explanation
(3,1), (3,5) and (2,4).

Constraints

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100
  • 1 <= k <= 99
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var countKDifference = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Number of Pairs With Absolute Difference K — Solution

Count Number of Pairs With Absolute Difference K solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Count Number of Pairs With Absolute Difference K is an easy coding problem on arrays, hash table and counting, asked in TCS, Wipro and Zoho interviews.

  • Difficulty: Easy
  • Topics: Arrays, Hash Table, Counting
  • Asked at: TCS, Wipro, Zoho
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Count the pairs of indices (i, j) with i < j and |nums[i] - nums[j]| == k.

Example 1

Input: nums = [1,2,2,1], k = 1
Output: 4
Explanation: Each 1 pairs with each 2.

Example 2

Input: nums = [1,3], k = 3
Output: 0

Example 3

Input: nums = [3,2,1,5,4], k = 2
Output: 3
Explanation: (3,1), (3,5) and (2,4).

Constraints

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

Hints for Count Number of Pairs With Absolute Difference K

  1. Hint 1

    The double loop is fine at this size and is the clearest statement of the problem.

  2. Hint 2

    The linear version keeps a frequency map and, for each element, adds the counts of x - k and x + k seen so far.

  3. Hint 3

    Counting before inserting attributes each pair to its later index exactly once.

How to solve Count Number of Pairs With Absolute Difference K

Every pair is determined by its two indices, so the direct double loop is exhaustive. The faster route turns the absolute difference into two lookups per element.

Approach

  1. Loop over all i < j and count the pairs whose absolute difference is k.
  2. For the linear version: sweep once with a tally, adding seen[x - k] + seen[x + k] before inserting x.

Why it works

|a - b| == k splits into a - b == k or b - a == k, which is why the fast version needs exactly two lookups. Counting before inserting means each pair is attributed to its later index once.

Complexity

  • Time — O(n²) directly, or O(n) with a tally
  • Space — O(1) directly, O(V) with a tally

Pitfalls

  • Looking up only x - k halves the count.
  • With k = 0 the two lookups coincide and would double count; the constraints exclude it here.

Reference solution

Python

from typing import List

def countKDifference(nums: List[int], k: int) -> int:
    seen = {}
    total = 0
    for x in nums:
        total += seen.get(x - k, 0) + seen.get(x + k, 0)
        seen[x] = seen.get(x, 0) + 1
    return total

Java

public static int countKDifference(int[] nums, int k) {
    Map<Integer, Integer> seen = new HashMap<>();
    int total = 0;
    for (int x : nums) {
        total += seen.getOrDefault(x - k, 0) + seen.getOrDefault(x + k, 0);
        seen.put(x, seen.getOrDefault(x, 0) + 1);
    }
    return total;
}

C++

int countKDifference(vector<int>& nums, int k) {
    unordered_map<int, int> seen;
    int total = 0;
    for (int x : nums) {
        total += seen[x - k] + seen[x + k];
        seen[x]++;
    }
    return total;
}

JavaScript

var countKDifference = function(nums, k) {
    var seen = {}, total = 0;
    for (var i = 0; i < nums.length; i++) {
        var x = nums[i];
        var a = seen[String(x - k)];
        var b = seen[String(x + k)];
        if (a !== undefined) total += a;
        if (b !== undefined) total += b;
        var key = String(x);
        seen[key] = (seen[key] === undefined ? 0 : seen[key]) + 1;
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets