Count duplicates in a JavaScript array

Question

This is actually a hackerrank interview question I have already solved but I need guidance on how to optimize it for the

1. Time
2. Space

Given an array of integers, your task is to count the number of duplicate array elements. Duplicate is defined as two or more identical elements. For example, in the array [1, 2, 2, 3, 3, 3], the two twos are one duplicate and so are the three threes.

Function Description

Complete the function countDuplicates in the editor below. The function must return an integer denoting the number of non-unique (duplicate) values in the numbers array.

countDuplicates has the following parameter(s):

numbers[numbers[0],...numbers[n-1]]: an array of integers to process

Constraints

1 ≤ n ≤ 1000
1 ≤ numbers[i] ≤ 1000, 0 ≤ i < n

Sample Input: [1, 3, 1, 4, 5, 6, 3, 2]
Sample Output: 2
Explanation: The integers 1 and 3 both occur more than once, so we return 2 as our answer.

function countDuplicates(original) {

  let counts = {},
    duplicate = 0;
  original.forEach(function(x) {
    counts[x] = (counts[x] || 0) + 1;
  });

  for (var key in counts) {
    if (counts.hasOwnProperty(key)) {
      counts[key] > 1 ? duplicate++ : duplicate;
    }
  }

  return duplicate;

}

Answer 1

Reduce time

You can improve the function's time complexity at the expense of memory by tracking the duplicates in a separate Set. This will reduce the number of iterations by the number of unique items in the input array, and increase the memory need by the same number.

A further improvement can be gained if you delete duplicates from the unique set as you go. This will bring the memory use down.

function countDuplicates(original) {
  const uniqueItems = new Set();
  const duplicates = new Set();
  for (const value of original) {
    if (uniqueItems.has(value)) {
      duplicates.add(value);
      uniqueItems.delete(value);
    } else {
      uniqueItems.add(value);
    }
  }
  return duplicates.size;
}



/* Test code not related to solution */
function test(name, func, data, result) {
  const output =  `${name} [${data.join(", ")}] : `;
  console.log(output + (func(data) === result ? "passed" : "failed")); 
}


test("1 duplicate ", countDuplicates, [9, 11, 12, 2, 7, 4, 2], 1);
test("1 duplicate ", countDuplicates, [6, 6, 6], 1);
test("2 duplicates ", countDuplicates, [0, 1, 4, 2, 7, 4, 2], 2);
test("3 duplicates ", countDuplicates, [0, 1, 4, 2, 7, 4, 2, 0], 3);
test("No duplicates ", countDuplicates, [0, 1, 4, 2, 7, 5, 8, 9], 0);

A look at memory.

Just out of interest I wanted to see the memory use. It turns out that the more unique items the lower the use (makes sense). The next snippet shows the memory use over 10000 calls to random arrays 1000 items long with a max range of item values to 10000.

function countDuplicatesMemory(original) {
  var maxSize = 0;
  const uniqueItems = new Set();
  const duplicates = new Set();
  for (const value of original) {
    if (uniqueItems.has(value)) {
      duplicates.add(value);
      maxSize = Math.max(maxSize, duplicates.size + uniqueItems.size);
      uniqueItems.delete(value);
    } else {
      uniqueItems.add(value);
      maxSize = Math.max(maxSize, duplicates.size + uniqueItems.size);
    }
  }
  return maxSize;
}



var memoryUse = 0;
var min = Infinity;
var max = 0;
const cycles = 10000;
const arraySize = 1000;
const maxRange = 10000;

for(let i = 0; i < cycles; i++){
  const arr = [];
  const range = Math.random() * maxRange | 0;
  for(let i = 0; i < arraySize; i++){
     arr.push(Math.random() * range | 0);
  }
  const mem = countDuplicatesMemory(arr);
  memoryUse += mem;
  min = Math.min(mem, min);
  max = Math.max(mem, max);
}
console.log("Mean memory use O(n * " + (memoryUse / cycles / arraySize).toFixed(3)+ ")");
console.log("Min memory use  O(n * " + (min / arraySize).toFixed(3)+ ")");
console.log("Max memory use  O(n * " + (max / arraySize).toFixed(3)+ ")");

The mean memory use is around O(n * 0.85)

These values are for a random set of values, there are cases where non random values may push the max memory just over O(n)