0

I have been asked in the interview to find repetitive elements in array. I have found using for loop, but the interviewer asked for more improved way to find out, with effect to performance with out for loop . I am beginner in exploring Java script. Could any one help to find other methods for finding repetitive elements in array. Below is my code for the answer

var a = [1,2,3,3,4,4,5,5,6,7,8,8,9,10,11,12];

var repeatElements = [];
for (var i=0;i<a.length;i++){
 for(var j=1+i; j<a.length;j++){
 if (a[i]===a[j]){
repeatElements.push(a[i]);
}

}
}
console.log(repeatElements);

I have checked the answer of this stack overflow question Get all unique values in a JavaScript array (remove duplicates) Whether using filter for finding repetitive would be more efficient way?

Manjula D
  • 145
  • 2
  • 8
  • https://stackoverflow.com/questions/840781/get-all-non-unique-values-i-e-duplicate-more-than-one-occurrence-in-an-array - some answers in there use a filter – Pete Dec 17 '19 at 11:03
  • Is the array sorted? – void Dec 17 '19 at 11:03
  • @void Given array sorted one. – Manjula D Dec 17 '19 at 11:04
  • @pete will check that one – Manjula D Dec 17 '19 at 11:05
  • 1
    You can increase performances by performing a single loop and keeping track of found items. Example using `reduce`: https://jsfiddle.net/9z7bLam1/ – briosheje Dec 17 '19 at 11:07
  • Just a side note: almost anything other than a for loop will be less performant. Using `reduce` or any other array prototype makes it faster on **BIGGER** array datasets. There is really not much to do on that case specifically to make it "more performant" other than using a dictionary. – briosheje Dec 17 '19 at 11:16
  • Ok. thanks for the details @ briosheje – Manjula D Dec 17 '19 at 11:17
  • @ManjulaD currently, you solution is most likely the most efficient on that dataset specifically. If no dataset was provided, you could've done better. Otherwise, it's likely the most efficient or almost the most efficient because the dataset is so small that adding a dictionary would just take longer than your solution. – briosheje Dec 17 '19 at 11:20

2 Answers2

1

A good way to do this in linear time is to use a frequency table:

var a = [1,2,3,3,4,4,5,5,6,7,8,8,9,10,11,12];

var frequencyTable = {};
var repeatElements = [];
for (var i=0; i<a.length; i++){
 if (frequencyTable[a[i]]){
  frequencyTable[a[i]]++;
  repeatElements.push(a[i]);
 } else {
  frequencyTable[a[i]] = 1;
 }
}

console.log(repeatElements);

This way you only loop through the array once.

volcanic
  • 312
  • 1
  • 6
  • Just a side note: this will most likely be **less performant** than the original solution due to the fact that the array is so small that there will be no benefit of using an hash table to keep track of found items. So, the correct answer, currently, is that the solution provided is likely the most efficient or that and the performance drop is neglibible on that dataset. See https://jsperf.com/find-dupes-array-primitives for more considerations. – briosheje Dec 17 '19 at 11:18
  • thanks for the js performance testing link. Got clarified @ briosheje – Manjula D Dec 17 '19 at 11:27
1

Your solution has O(n^2) complexity. I think interviewer was expecting you to provide O(n) solution, which involves usage of some sort of dictionary of repetitive items. That looks like this:

const a = [1,2,3,3,4,4,5,5,6,7,8,8,9,10,11,12];

function getRepetitives(arr) {
  const itemsDuplicates = {}
  
  arr.forEach(item => {
    itemsDuplicates[item] = itemsDuplicates.hasOwnProperty(item) 
      ? itemsDuplicates[item] + 1
      : 1 
  })
  
  const repetitives = Object.entries(itemsDuplicates).filter(([ k ,v ]) => v > 1).map(([k]) => k)
  
  return repetitives
}

console.log(getRepetitives(a))
lankovova
  • 1,396
  • 8
  • 15
  • @Addis No it's not. Basically there will be always `O(n)` even if you are iterating through initial array 100 times, because in huuuuuuge amounts of data it does not matter much. On the other hand if you have nested loop (like one in the answer) the complexity will grow way much faster resulting in `O(n^2)`, for three nested loops - `O(n^3)` and so on. I suggest you to take a read about basic complexity calculation, this is very helpful in every day programming. – lankovova Dec 17 '19 at 11:45
  • I got your point. I wanted to say 3* O(n) actually, while it was possible to it with just a single loop. While linear, it's not as efficient as 1* O(n). – Addis Dec 17 '19 at 11:50
  • 1
    @Addis Sure. As less operations you perform - the less time algorithm will consume. But speaking in big o notation, there is no such thing as `3 * O(n)`, it is converted into `O(n)` dropping the 3. Looking at my answer I can already tell the way it can be optimized (for example using `reduce` instead of `filter - map` pair). – lankovova Dec 17 '19 at 12:40