Overview

Given a sequence \(A\) consisting of \(N\) integers, the problem asks to find the number of pairs of elements whose absolute difference is exactly \(K\).

Analysis

Naive Approach

The simplest method is to check all pairs of two elements \((A_i, A_j)\) using a double loop. However, with this method the number of combinations is \(\frac{N(N-1)}{2}\), resulting in a time complexity of \(O(N^2)\). Given the constraint \(N \le 2 \times 10^5\), \(N^2\) reaches approximately \(4 \times 10^{10}\), which will not finish within the time limit (resulting in TLE).

Efficient Approach

The fact that the absolute difference is \(K\) means that for a given element \(x\), its pair partner must be either \(x + K\) or \(x - K\). Here, if we only count pairs of the form “\(x\) and \(x + K\)” for every \(x\), we can cover all pairs without duplication (since \(K \ge 1\), \(x\) and \(x + K\) are always distinct).

Specifically, we proceed with the following steps: 1. Record in advance how many times each value appears in the sequence. 2. For each value \(x\) in the sequence, let \(C_x\) denote its number of occurrences. 3. If the value \(x + K\) appears \(C_{x+K}\) times in the sequence, there are \(C_x \times C_{x+K}\) such pairs. 4. Sum this value over all \(x\).

With this method, we only need to check each value once, enabling fast processing.

Algorithm

We use a solution based on a hash map (in Python, dict or collections.Counter).

1. Counting: Scan the sequence \(A\) and store the occurrence count of each value in a hash map.
2. Aggregation: For each key \(x\) in the hash map, repeat the following:
   • If the key \(x + K\) exists in the hash map, add (occurrence count of x) × (occurrence count of x + K) to the answer.
3. Output: Output the final total.

Complexity

• Time Complexity: \(O(N)\)
  • Reading the sequence takes \(O(N)\), building the hash map takes \(O(N)\), and checking each element of the hash map takes at most \(O(N)\). Since hash map operations (insertion and lookup) are \(O(1)\) on average, the overall complexity is \(O(N)\).
• Space Complexity: \(O(N)\)
  • The hash map storing each value can have at most \(N\) entries, consuming \(O(N)\) memory.

Implementation Notes

• Counter class: Using Python’s collections.Counter allows you to concisely count the occurrences of elements from a list.

• Avoiding duplicate counting: By only checking \(x + K\) in the loop, we perform a one-directional search “from the smaller value to the larger value,” preventing the same pair from being counted twice.

• Fast input: Since \(N\) can be large, reading all input at once using sys.stdin.read().split() or similar methods can reduce execution time.

  Source Code

import sys
from collections import Counter

def solve():
    # 入力を標準入力から一括で読み込む（高速化のため）
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 数列の要素数, K: 目標とする差
    N = int(input_data[0])
    K = int(input_data[1])
    # A: 数列の各要素
    A = list(map(int, input_data[2:]))
    
    # 各数値の出現回数をカウントする
    counts = Counter(A)
    
    ans = 0
    # 数列に含まれるユニークな各数値 x についてループ
    for x in counts:
        # x + K が数列内に存在するか確認する
        # x + K を探すことで、すべてのペア {x, x + K} を重複なく数え上げることができる
        # (K >= 1 なので、x と x + K は必ず異なる値になる)
        target = x + K
        if target in counts:
            # x の出現回数と target の出現回数の積を足す
            ans += counts[x] * counts[target]
            
    # 結果を出力
    print(ans)

if __name__ == "__main__":
    solve()

This editorial was generated by gemini-3-flash-preview.