3

I have a sorted Array:

let mySortedArray = [1,1,5,6,8,8,9,25,25]

I want to remove any duplicates from this array in O(1) time and space complexity. First of all, is this even possible?

My solution is the following: I convert the array to a set and any duplicates are just removed.

let mySet = new Set(myArray);

What would the time and space complexity of that be?

And if I were to convert the set back to an Array:

let myNewArr = Array.from(mySet);

What would the time and space complexity of the whole method then be?

Would this be the most optimal way of removing any duplicates of an array or would there be a better one?

EDJ
  • 843
  • 3
  • 17
  • 37
  • I don't believe this is possible in `O(1)`, as in order to know if there are any other elements which are duplicated you would have to go through the entire array, looking at each element at least once. Thus, I believe your only going to be able to get `O(N)` for your time complexity. [This](https://stackoverflow.com/questions/31091772/javascript-es6-computational-time-complexity-of-collections) also may provide further insight – Nick Parsons Nov 21 '18 at 09:53
  • I don't think O(1) is possible for this. Creating a Set from an array uses the iterator interface iirc, so the complexity is O(n) I think, since every element of the array still gets looped over to add it to the Set. Since the array is already sorted, there's probably some way to get a fraction of O(n), but you still have to check at least two elements since we don't know yet how many unique elements there are. – Shilly Nov 21 '18 at 09:56
  • Since I don't support Set() yet, I use the following general function, which is O(n) i think: `const unique = () => { const seen = {}; return item => { const json = JSON.stringify( item ); return seen.hasOwnProperty( json ) ? false : ( seen[ json ] = true ); }; };` and then `mySortedArray.filter( unique() );`. – Shilly Nov 21 '18 at 09:57
  • There is some related info at this post:[Remove duplicate values from JS array](https://stackoverflow.com/questions/9229645/remove-duplicate-values-from-js-array). – prasad_ Nov 21 '18 at 10:33
  • 1
    Since you already have a sorted array I guess the following: `[1,1,5,6,8,8,9,25,25].filter((item,index,all)=>all[index-1]!==item)` will be best from the [related post](https://stackoverflow.com/questions/9229645/remove-duplicate-values-from-js-array) – HMR Nov 21 '18 at 13:18

0 Answers0