Find duplicates in an array using javascript
Problem :
Given an array of positive integers find all the duplicate elements.
Algorithm :
- Iterate over the array using
forEach
- Find if there is a duplicate for the element using
indexOf
indexOf
takes two arguments first the element and the second one is the starting index- We provide the starting index as the
index + 1
where index is the index of the current element - We will find if the same element exists on the
right hand side
of that element or not -
If there’s a
duplicate
and the element is not already being added to theresult
then push it to the array.
- Find if there is a duplicate for the element using
Solution :
Sorry, but this algorithm is not O(1). It’s also not O(n).
It is actually O(n^2). The data.indexOf call in the loop effectively makes the comparisons done be proportional to data.length * data.length = n^2.