Count pairs in an array in javascript

Perhaps there is a faster/better way to calculate this than this O(2n) solution, but it's something:

var ar1 = [10, 20, 20, 10, 10, 30, 50, 10, 20] // return 3 (2 pairs of 10 and 1 pair of 20)
var ar2 = [1, 1, 3, 1, 2, 1, 3, 3, 3, 3] // return 4 (2 pairs of 1 and 2 pairs of 3)

function countPairs(ar) {
  var obj = {};

  ar.forEach(item => {
    obj[item] = obj[item] ? obj[item] + 1 : 1;
  });
  
  return Object.values(obj).reduce((acc, curr) => {
    acc += Math.floor(curr / 2)
    return acc;
  }, 0);
}

console.log(countPairs(ar1))
console.log(countPairs(ar2))

This first calculates the number of occurences for each number and stores them in an Object. Once that is done, we reduce over the values and return the quotient from the division with 2 (to get the number of pairs in total).

Note: I removed the first argument from your function, because the array length is not needed as an argument. It can be obtained from the array you pass directly.


We can achieve this in O(n) time. Maintain an object which keeps track whether a number have been found before, if it was found before, then it makes up a pair, so we increment the pairs count. If not we make the entry of that number in the object 1

function countPairs(arr) {
    let pairs = 0;
    const obj = {};
    arr.forEach(i => {
        if (obj[i]) {
            pairs += 1;
            obj[i] = 0;
        } else {
            obj[i] = 1;
        }
    });
    return pairs;
}

Tags:

Javascript