0

Suppose I have an array like [1,1,2,2,3,4]

I want to get [3,4] by using a function like function answer(data,n)

abid hossain
  • 25
  • 1
  • I want to get only [3,4] – abid hossain Jul 08 '22 at 05:51
  • 1
    @RobbyCornelissen agreed. Re-opened – Phil Jul 08 '22 at 05:57
  • @connexo go through array, count occurrence of each item with a map. It's linear. Go through map and get all with count of 1. Or go through array and check which elements have a count of 1 - same thing. Both should be linear. It's `O(n)` at the end. – VLAZ Jul 08 '22 at 06:03
  • @VLAZHow would you do the counting without iterating the mapped array repeatedly? – connexo Jul 08 '22 at 06:06
  • 1
    @connexo `for (x of arr) map.set(x, (map.get(x) ?? 0) + 1)` or `for (x of arr) obj[x] = (obj[x] ?? 0) + 1` for using an object. Map operations should be `O(1)`. – VLAZ Jul 08 '22 at 06:09

1 Answers1

2

I would reduce() down to a map with the elements as keys, and boolean values to indicate whether the element has been seen before. Then it's just a matter of filtering out the entries that are duplicates:

const data = [1, 1, 2, 2, 3, 4];

const result = [
  ...data.reduce((a, v) => a.set(v, a.has(v)), new Map())
].filter(([_, v]) => !v).map(([k]) => k);

console.log(result);
Robby Cornelissen
  • 91,784
  • 22
  • 134
  • 156
  • From that linked dupe: `arr.filter(x => arr.indexOf(x) === arr.lastIndexOf(x))`. I'd be curious tho if there is a method that's better O(n)-wise. – connexo Jul 08 '22 at 06:02
  • 1
    @connexo The one-liner is `O(n^2)`: the `.filter()` is `O(n)` and for each item visited it `indexOf` and `lastIndexOf` which are both `O(n)` themselves. So, `n*2n` total which simplifies to `O(n^2)` after dropping the constant. That's just analysis of the operations' complexity. In reality, `arr.indexOf(x)` and `arr.lastIndexOf(x)` are guaranteed to *at most* visit `length+1` elements. Consider if `x` is first - then `indexOf` will find it immediately, `lastIndexOf` will traverse the whole array. And vice versa. – VLAZ Jul 08 '22 at 06:21
  • @VLAZ You're right. `O(n^2)` indeed for the `indexOf` approach. – Robby Cornelissen Jul 08 '22 at 06:22
  • 1
    @RobbyCornelissen still too much for this problem. – VLAZ Jul 08 '22 at 06:24
  • Seems to boil down to code complexity vs runtime complexity. The one-liner only takes me 2 seconds to understand what it does; none of the other solutions suggested seems that easy to grab. – connexo Jul 08 '22 at 06:28
  • @connexo I'd rather write 3 lines of JsDoc than introduce an operation of unneeded quadratic complexity... – Robby Cornelissen Jul 08 '22 at 06:30
  • Consider adding those 3 lines to your snippet then :) – connexo Jul 08 '22 at 06:31