CodingGyan

Count Pairs with Difference k

medium Arrays

Problem

Count the pairs of positions (i, j) with i < j where the absolute difference of the two numbers is exactly k (k >= 1). Equal numbers at different positions count as different pairs. Use a hash map, not two loops.

Constraints

  • 1 <= n <= 10^5
  • 1 <= k <= 10^9

Examples

Input

4
1 2 2 1
1

Output

4

Solutions

Best approachTime O(n)Space O(n)

Two loops take O(n^2). The map lets us ask in O(1) how many earlier numbers are k away. Because k >= 1, value - k and value + k are never the same key, so no pair is counted twice.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Count pairs.
 * Input   : n, array, k.
 * Output  : The count.
 * Approach: Hash map.
 * Time    : O(n)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static long solve(int[] a, int k) {
        // Step 1: The map counts how many times each number was seen so far.
        java.util.Map<Integer, Integer> seen = new java.util.HashMap<>();
        long pairs = 0;
        for (int value : a) {
            // Step 2: An earlier number that is exactly k smaller or k bigger makes a pair with this number.
            pairs += seen.getOrDefault(value - k, 0);
            pairs += seen.getOrDefault(value + k, 0);
            seen.merge(value, 1, Integer::sum);
        }
        return pairs;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        int[] a = new int[size];
        for (int i = 0; i < size; i++) {
            a[i] = scanner.nextInt();
        }
        int k = scanner.nextInt();
        System.out.println(solve(a, k));
    }
}
Hints (1)
  1. Why must k be at least 1 here?

Try these next