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;
}