5
\$\begingroup\$

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;

}

\$\endgroup\$
  • 1
    \$\begingroup\$ The code is perfect, can´t do better than O(n) time. You could however use an array instead of an object to count, as you know the numbers only go up to 1000. \$\endgroup\$ – juvian Sep 4 '18 at 14:25
3
\$\begingroup\$

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)

\$\endgroup\$
  • \$\begingroup\$ I would recommend this if he was working with bigger ranges on the elements, but this is slower than his current solution for elements between 0 and 1000 \$\endgroup\$ – juvian Sep 4 '18 at 19:35
  • \$\begingroup\$ @juvian The question asked for a review in terms of time and space, not performance. In JavaScript the best time complexity often does not result in the most performant code. If the metric was to be performance then there is plenty of room in the OP's code for improvement, depending on the engine it is run on. \$\endgroup\$ – Blindman67 Sep 4 '18 at 20:16
  • \$\begingroup\$ Both your time and space optimization rely on the engine it runs on. I fail to see how this is better in terms of time and space than original code \$\endgroup\$ – juvian Sep 4 '18 at 20:19
  • \$\begingroup\$ @juvian Time complexity is a measure of the algorithm independent of the device and language it is run on. \$\endgroup\$ – Blindman67 Sep 4 '18 at 20:29
  • \$\begingroup\$ You are relying on data structures (Set), access time and delete rely on the implementation (browser engine) it runs on. If set is implemented with a tree with O(log n) operations, then using object that is implemented with hash set would have lower time complexity. \$\endgroup\$ – juvian Sep 4 '18 at 20:31

protected by Jamal Jun 29 at 22:39

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.