Count Pairs with Equal Elements

Title: Count Pairs with Equal Elements

In this guide, you will learn how to count pairs with equal elements in a Java array efficiently. This is a classic interview warm-up problem that checks whether you reach for a hash-based frequency count instead of a brute-force nested loop.

Given an array of integers, the task is to count how many index pairs (i, j) with i < j satisfy numbers[i] == numbers[j]. We will build a frequency map in a single pass, then convert each value’s frequency into a pair count using a simple combinatorics formula.

Understanding the Problem

A pair is defined by two distinct positions in the array, not by two equal values you happen to notice; every combination of indices where the values match counts, even if the same value appears far apart. For an array of size n, comparing every pair directly with two nested loops costs O(n^2) time, which becomes slow once the array has thousands of elements.

The key realization is that the number of pairs depends only on how many times each distinct value appears, never on where it sits in the array. If a value appears count times, it contributes exactly count * (count - 1) / 2 pairs, the standard n choose 2 combination formula applied to that value’s positions.

Order inside a pair does not matter either; (i, j) and (j, i) are the same pair, so the formula above already counts unordered pairs and must never be doubled.

Approach / Algorithm Steps

1. Validate the input: throw IllegalArgumentException if numbers is null.
2. Create a HashMap<Integer, Integer> named frequency to record how many times each value has appeared so far.
3. Iterate through numbers once, updating frequency with frequency.getOrDefault(value, 0) + 1 for the current value.
4. After the single pass, initialize a long pairCount to zero.
5. Iterate over frequency.values() and add count * (count - 1) / 2 to pairCount for every distinct value’s frequency.
6. Return pairCount once every distinct value has been processed.

Java Program

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

public class CountPairsWithEqualElements {

    public static long countPairs(int[] numbers) {
        if (numbers == null) {
            throw new IllegalArgumentException("Input array must not be null");
        }

        Map<Integer, Integer> frequency = new HashMap<>();
        for (int value : numbers) {
            frequency.put(value, frequency.getOrDefault(value, 0) + 1);
        }

        long pairCount = 0;
        for (int count : frequency.values()) {
            pairCount += (long) count * (count - 1) / 2;
        }
        return pairCount;
    }

    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 1, 1, 3};
        long result = countPairs(numbers);
        System.out.println("Number of pairs: " + result);
    }
}

Explanation of the Program

• frequency.getOrDefault(value, 0) + 1 inserts or updates the running count for value in a single pass, which keeps the first loop at O(n) time.
• The second loop runs once per distinct value, never once per pair, so the algorithm never compares two array positions directly.
• pairCount is declared as long because count * (count - 1) can exceed Integer.MAX_VALUE when a single value repeats tens of thousands of times.
• The null check at the top fails fast with a clear message instead of letting a NullPointerException surface deep inside the for-each loop.

Step-by-Step Trace

For numbers = {4, 4, 2, 4, 2, 5}, the target output is 4 pairs. The table below traces how frequency is built one array element at a time.

After processing index i, frequency.get(numbers[i]) always holds the exact number of times that value has appeared in numbers[0..i], which is exactly the count the second loop later converts into pairs.

Examples

The following examples run the algorithm on three different frequency distributions, from no duplicates at all to a single value repeated across the whole array.

Example 1: Array with No Duplicates

int[] numbers = {5, 8, 3, 9};
System.out.println(countPairs(numbers)); // 0

Every value in this array appears exactly once, so frequency never exceeds 1 for any key and count * (count - 1) / 2 evaluates to 0 for all of them.

Example 2: Array Where Every Element Repeats

int[] numbers = {7, 7, 7, 7};
System.out.println(countPairs(numbers)); // 6

The value 7 appears 4 times, so it alone contributes 4 * 3 / 2 = 6 pairs, matching the full output since no other value is present.

Example 3: Mixed Frequencies

int[] numbers = {1, 2, 3, 1, 1, 3};
System.out.println(countPairs(numbers)); // 4

The value 1 appears 3 times and contributes 3 pairs, the value 3 appears twice and contributes 1 pair, and the value 2 appears once and contributes 0 pairs, for a total of 4.

Common Mistakes to Avoid

These are the mistakes candidates actually make when solving this exact problem, not generic advice about testing your code.

• Counting ordered pairs instead of unordered pairs – looping over every i and j where i != j counts each equal pair twice, doubling the result. Only count when i < j, or use the frequency formula so each pair is counted once by construction.
• Forgetting the divide by 2 in the combination formula – writing count * (count - 1) without dividing by 2 produces a value exactly twice too large. Always apply count * (count - 1) / 2, never just the product.
• Using int for the running pair count – count * (count - 1) can overflow a 32-bit int when one value repeats tens of thousands of times in a very large array. Accumulate the result in a long.
• Re-counting frequency inside the outer loop – calling a nested scan to count occurrences for every element turns the algorithm back into O(n^2). Build the frequency map once in a single pass, then compute pairs from it.
• Ignoring the null check and relying on the for-each loop to fail – a null array throws a raw NullPointerException deep inside the loop with no context. Validate numbers at the top of the method instead.

Edge Cases to Test

Walk through these inputs out loud during an interview before you are asked; it signals that you think about boundaries unprompted.

• Empty array
• Single-element array
• All elements identical
• No duplicate elements
• Array containing negative numbers
• Integer.MIN_VALUE / Integer.MAX_VALUE present
• Very large array with one value repeated many times
• Null array reference

Integer.MIN_VALUE and Integer.MAX_VALUE matter only because they are valid HashMap keys like any other int value; they do not risk overflow themselves, but a value repeated enough times to make count * (count - 1) overflow does, which is why pairCount must stay a long.

Additional Considerations

The frequency-map approach runs in O(n) time: one pass to build frequency and a second pass over at most n distinct values to total the pairs. Space usage is O(d), where d is the number of distinct values, which is never worse than O(n).

A brute-force double loop needs no extra memory but costs O(n^2) time, so the frequency map trades a small, bounded amount of memory for a large reduction in running time once the array grows past a few hundred elements.

When the value range is known and bounded, for example scores from 0 to 100, a plain int[] counting array avoids HashMap boxing overhead entirely and is faster in practice than this general-purpose solution.

Interview Follow-up Questions

These are the natural follow-ups an interviewer uses to probe whether you understand the approach or just memorized it.

• What if the array is sorted? – scan once and count the length of each run of equal consecutive values, converting each run length into pairs with the same combination formula, without needing a HashMap at all.
• What if you need pairs that sum to a target value instead of equal elements? – replace the frequency lookup with a complement lookup, checking how many times target - numbers[i] has already appeared.
• What if the input arrives as a stream of unknown length? – keep a running frequency map and add the current count for a value to a running total every time that value is seen, before incrementing its count.
• What if the array has billions of elements and does not fit in memory? – sort the data externally in chunks, merge it back into sorted order, then count equal runs in a single streaming pass instead of holding every value in a hash map.
• What if you must solve this with O(1) extra space and cannot modify the input? – this generally requires the array to already be sorted, or accepting O(n^2) time, since an unsorted array with unbounded values cannot be counted correctly without either extra memory or reordering.

Conclusion

Counting pairs with equal elements comes down to one insight: group by value with a frequency map, then convert each group’s size into pairs with a single formula. Once you internalize that, the same pattern unlocks a whole family of counting problems.

Try adapting this exact code to count pairs with equal remainders when divided by k, which is a close cousin of this problem and a common follow-up on its own. You can learn more about array-based counting techniques in the Arrays tutorials on dailyjavaconcept.com.