# Hackerrank Solution: Sherlock and Pairs

Original Problem

Sherlock is given an array of $$N$$ integers ($$A_0, A_1 \dots A_{N-1}$$) by Watson. Now Watson asks Sherlock how many different pairs of indices $$i$$ and $$j$$ exist such that $$i$$ is not equal to $$j$$ but $$A_i$$ is equal to $$A_j$$.

That is, Sherlock has to count the total number of pairs of indices $$(i,j)$$ where $$A_i=A_j$$ and $$i\neq j$$.

## Input Format

The first line contains $$T$$, the number of test cases. $$T$$ test cases follow.

Each test case consists of two lines; the first line contains an integer $$N$$, the size of array, while the next line contains $$N$$ space separated integers.

## Output Format

For each test case, print the required answer on a different line.

## Constraints

• $$1\leq T \leq 10$$
• $$1\leq N\leq 10^5$$
• $$1\leq A[i]\leq 10^6$$

## Solution

The easiest solution for this problem is an $$O(n^2)$$ algorithm, that loops over the array twice and checks if the condition $$A_i=A_j$$ and $$i\neq j$$ holds for each pair $$(i, j)$$:

function solve(a) {
let c = 0;
for (let i = 0; i < a.length; i++) {
for (let j = 0; j < a.length; j++) {
if (i !== j && a[i] == a[j]) {
c++;
}
}
}
return c;
}

While this algorithm works for the first test cases, it fails later since the constraints state that the number of elements in the array can contain up to $$10^5$$ elements.

But if we count each element in the array, we know that for each unique value $$k$$ in the array and its count $$c_k$$, exactly $$c_k^2 - c_k$$ elements are possible, as it is a full permutation reduced by the number of occurences for $$i=j$$. So, an $$O(n)$$ solution can be found by storing all elements of the array in a hashmap and then sum over all unique numbers:

$\sum_{k\in A} c_k(c_k - 1)$

An implementation can then be stated like this:

function solve(a) {
let s = 0, c = {};
for (let i = 0; i < a.length; i++) {
c[a[i]] = (c[a[i]] || 0) + 1;
}
for (let k in c) {
s+= c[k] * c[k] - c[k];
}
return s;
}

This solution has a space complexity of $$O(n)$$. When we sort the array in-place first in $$O(n\log n)$$, we can then solve the problem in $$O(n)$$ with $$O(1)$$ additional space requirements:

function solve(a) {
a.sort((x, y) => x - y);
let s = 0, c = 1, p = a[0];
for (let i = 1; i < a.length; i++) {
if (a[i] == p) {
c++;
} else {
s+= c * c - c;
c = 1;
}
p = a[i];
}
return s + c * c - c;
}

« Back to problem overview