Count Pairs with Difference K

Title: Count Pairs with Difference K

Counting pairs with a given difference is a classic array problem that shows up often in coding interviews. In this guide, you will learn how to count every pair of elements in an array whose absolute difference equals a target value k, using an efficient HashMap based approach instead of a slow nested loop.

You will walk through the approach step by step, trace the algorithm on a sample input, and see the common mistakes and edge cases that interviewers love to probe.

Understanding the Problem

Given an integer array arr and a non-negative integer k, you need to count how many pairs of elements (arr[i], arr[j]) exist such that Math.abs(arr[i] - arr[j]) == k and i != j. Each unordered pair should be counted exactly once, even when the array contains duplicate values.

A brute force solution compares every pair with two nested loops, which costs O(n^2) time. The goal is to solve it in a single pass using a frequency map, bringing the time down to O(n).

Approach to Count Pairs with Difference K

1. Handle the trivial cases first: if arr is null, has fewer than two elements, or k is negative, return 0.
2. Build a HashMap<Integer, Integer> named freq that maps each distinct value in arr to how many times it occurs.
3. Iterate over every unique value num in freq along with its occurrences count.
4. If k is 0, add occurrences * (occurrences - 1) / 2 to the running total, since that counts every way to pick two equal elements from the same group.
5. Otherwise, check whether freq contains the key num + k. If it does, add occurrences * freq.get(num + k) to the running total.
6. Return the running total once every unique value has been processed.

Java Program

import java.util.HashMap;
import java.util.Map;

public class CountPairsWithDifferenceK {

    public static int countPairsWithDiffK(int[] arr, int k) {
        if (arr == null || arr.length < 2 || k < 0) {
            return 0;
        }

        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : arr) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }

        int count = 0;
        for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
            int num = entry.getKey();
            int occurrences = entry.getValue();

            if (k == 0) {
                count += occurrences * (occurrences - 1) / 2;
            } else if (freq.containsKey(num + k)) {
                count += occurrences * freq.get(num + k);
            }
        }

        return count;
    }

    public static void main(String[] args) {
        int[] arr = {1, 5, 3, 4, 2};
        int k = 2;

        int result = countPairsWithDiffK(arr, k);
        System.out.println("Pairs with difference " + k + ": " + result);
    }
}

Explanation of the Program

• countPairsWithDiffK first guards against a null or too-short array, and against a negative k, returning 0 immediately in those cases.
• The freq map is built in a single pass over arr using getOrDefault, so duplicate values accumulate a correct occurrence count instead of overwriting each other.
• The second loop walks freq.entrySet() once, so every unique value is visited exactly one time no matter how many duplicates it has.
• When k is 0, the code uses the combination formula occurrences * (occurrences - 1) / 2 instead of treating 0 like any other difference.
• For a non-zero k, freq.containsKey(num + k) looks only in the positive direction, which is enough because every valid pair gets discovered from its smaller member.
• main wires the method to a sample array and difference, then prints the resulting pair count.

Step-by-Step Trace

Trace the algorithm on arr = {7, 2, 9, 4, 11, 1} with k = 5; the expected output is 2 pairs. The freq map is built first, so every lookup below already sees the full set of occurrences.

At the end of each iteration, count holds the total number of valid pairs found among all unique values visited so far, since freq was fully built before the loop began, so every num + k lookup is accurate regardless of visit order.

Examples

Example 1: Pairs With Difference Zero

When k is 0, the method counts pairs of equal elements using the combination formula.

int[] arr = {4, 4, 4, 2, 2, 9};
int k = 0;
// countPairsWithDiffK(arr, k) returns 4
// pairs: (4,4), (4,4), (4,4), (2,2)

Example 2: Negative Numbers in the Array

Negative values work the same way because the sign never matters; the lookup num + k finds the matching partner regardless of sign.

int[] arr = {-3, -1, -7, 2, 5};
int k = 4;
// countPairsWithDiffK(arr, k) returns 1
// pair: (-7, -3)

Example 3: Consecutive Integers

Consecutive integers with k = 1 produce a pair for every adjacent value, which is a good sanity check for the algorithm.

int[] arr = {1, 2, 3, 4, 5, 6, 7};
int k = 1;
// countPairsWithDiffK(arr, k) returns 6
// pairs: (1,2), (2,3), (3,4), (4,5), (5,6), (6,7)

Common Mistakes to Avoid

These are the mistakes that most often slip into a first attempt at this problem.

• Treating k == 0 like any other difference – calling freq.get(num + 0) as if it were a different group gives occurrences * occurrences pairs, counting elements against themselves. For arr = {5, 5, 5} this wrongly returns 9 instead of 3. Handle k == 0 separately with occurrences * (occurrences - 1) / 2.
• Using a HashSet instead of a HashMap – a HashSet only tracks whether a value exists, not how many times, so duplicate values get undercounted. For arr = {4, 4, 4, 2, 2, 9} with k = 0 a set based check returns 0 instead of 4. Use HashMap<Integer, Integer> to track occurrences.
• Checking both num + k and num – k – looking in both directions finds every pair twice, except when k == 0, doubling the final count. Check only num + k and let the loop reach the smaller member of every pair naturally.
• Allowing a negative k through unchecked – a negative k silently matches values going the wrong direction and can double count alongside the positive side. Validate k >= 0 at the start of the method, or normalize it with Math.abs(k) before counting.
• Comparing arr[i] – arr[j] == k in a brute force rewrite – signed subtraction without Math.abs only catches the pairs where the larger value comes first, silently dropping the rest. Compare Math.abs(arr[i] - arr[j]) == k, or stick with the map based approach that avoids the issue entirely.

Edge Cases to Test

Walk through these inputs before calling the solution finished.

• Empty array
• Single element array
• k equal to 0
• Duplicate values in the array
• All elements identical
• Negative numbers present
• Negative k value
• Integer.MAX_VALUE present (num + k overflow risk)

Additional Considerations

The frequency map approach runs in O(n) time: one pass to build freq and one pass over its unique keys, each HashMap operation taking amortized O(1). Space usage is O(n) in the worst case, when every element in arr is distinct.

A sorted array admits a two pointer alternative: sort arr first, then advance two indices so their difference trends toward k. That costs O(n log n) for the sort but only O(1) extra space, which is worth it when memory is tighter than time.

Watch for overflow when num is close to Integer.MAX_VALUE and k is positive; num + k can wrap around to a negative number and match an unrelated key. Widening the lookup to long removes the risk entirely.

Interview Follow-up Questions

An interviewer rarely stops at the base problem. Expect at least one of these follow ups.

• What if the array is sorted? – use two pointers that both move forward, since a sorted array lets you grow or shrink the gap between them without rescanning from the start.
• What if you need the actual pairs, not just the count? – store each matching (num, num + k) combination in a list as you find it during the map iteration, instead of only accumulating a count.
• What if k can change on every query against the same fixed array? – sort arr once and binary search for num + k on each query, giving O(log n) per query instead of rebuilding a map every time.
• What if the array arrives as a live, unbounded stream? – maintain the frequency map incrementally as elements arrive, checking num + k and num - k against the map built so far on each new element.
• What if the array has billions of elements and does not fit in memory? – sort the data in external chunks and merge with a two pointer scan across sorted runs, since difference k pairs only ever involve nearby values once the data is ordered.

Conclusion

Counting pairs with a fixed difference comes down to remembering what you have already seen. A HashMap of occurrences turns an O(n^2) nested loop into a single pass, and handling k == 0 as its own case keeps the combination math correct.

Try adapting countPairsWithDiffK to return the pairs themselves, or to work against a sorted array with two pointers, to make sure the idea has fully clicked. You can learn more about arrays here: Arrays.