Get started

Count Number of Pairs With Absolute Difference K — Easy Problem & Solution

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

  • 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

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

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue