Overview

Select 2 distinct elements from a sequence and efficiently count the number of pairs whose absolute difference is exactly \(K\), taking duplicate elements into account.

Analysis

If we naively check all pairs \((i, j)\) (\(i<j\)), the number of combinations is \(\frac{N(N-1)}{2}\), which results in \(O(N^2)\) for up to about \(2\times 10^5\) elements, and will certainly result in a time limit exceeded.

The key observation is as follows:

• “Absolute difference is \(K\)” means it suffices to count pairs of the form \((x, x+K)\).
  This is because \(|a-b|=K\) means either \(a=b+K\) or \(b=a+K\), and in either case, the pair is uniquely determined as “the smaller value \(x\) and the larger value \(x+K\).”
• Since the same value can appear multiple times, we can count them collectively using frequencies.
  For example, if \(x\) appears \(c\) times and \(x+K\) appears \(d\) times, there are \(c \times d\) pairs with a difference of \(K\) (combinations of their respective positions).

Concrete example: \(A=[1,1,4,4,4]\), \(K=3\)
- \(1\) appears 2 times, \(4\) appears 3 times, so the number of \((1,4)\) pairs is \(2\times 3=6\).

With this approach, for each value \(x\) we only need to efficiently look up “how many times does \(x+K\) appear,” and by managing frequencies with a hash map (dictionary), this can be solved in approximately \(O(N)\).

Algorithm

1. Count the occurrences of each value in the sequence \(A\) using a Counter (dictionary). cnt[v] = number of occurrences of v.
2. Initialize the answer ans=0.
3. For each value \(x\) contained in cnt:
   • Let \(c\) be the count of \(x\), and \(d = \text{cnt}[x+K]\) be the count of \(x+K\) (0 if it doesn’t exist).
   • Add ans += c * d.
4. Output ans.

In this counting method, we always count only “the smaller value \(x\) and the larger value \(x+K\),” so the same pair is never counted twice (this naturally satisfies the condition of not treating \((x, x+K)\) and \((x+K, x)\) as separate pairs).

Complexity

• Time complexity: \(O(N)\) (Counter construction is \(O(N)\), and letting \(M\) be the number of distinct values, the loop is \(O(M)\) where \(M \le N\))
• Space complexity: \(O(M)\) (storing frequencies for each distinct value)

Implementation Notes

• collections.Counter is convenient for frequency management.

• By writing cnt.get(x + K, 0), you can safely return 0 for keys that don’t exist.

• ans can be on the order of \(O(N^2)\) at most, but since Python integers do not overflow, this is not a problem.

  Source Code

import sys
from collections import Counter

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    cnt = Counter(A)

    ans = 0
    for x, c in cnt.items():
        ans += c * cnt.get(x + K, 0)

    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.