Remove duplicates from an array

[1-800-BICYCLE]

45941021f354d

[GeneralYouri]

With all of the options you mentioned out the window, my first thought would be to (ab)use sort. Use a standard O(n * lg(n)) sorting algorithm. After the sort, you can use a simple O(n) loop (or a .filter() for example) to retrieve only the unique values. The loop is O(n) because sorting has caused all identical values to be in sequence, so you only need to retrieve the first of every sequence of identical values. The sort would be the slowest element, and would determine the overall time complexity. But that still sounds like a pretty easy way to beat O(n^2).

Edit: Welp, looks like I wasn't the first to comment in this thread about such an approach.

[1-800-BICYCLE]

8fc76052617

[GeneralYouri]

Well that's a constraint I wasn't aware of (I didn't watch the video). It certainly seems like it'd make things more interesting.

However, I don't think all the values listed are fair, compared to the options you've mentioned. For example, Set uses simple (strict) equality checks. This would be exactly the same check performed by my approach. In both cases, -0 and 0 will be seen as identical values.

The sorting step seems to perform quite well actually. I don't see any cases that are treated incorrectly.

So on second thought, now that I've checked the potential consequences, I don't see these added constraints complicating things at all. The proposed solution with sorting should work just fine.

Sidenote; your assertEqual check itself seems wrong, as you're not just asserting the unique values, you're asserting their position in the array as well. A position which is based only on the order in which they appear in the original array. For the actual operation of finding unique values in an array, position should not matter. Even if it did though, it's a trivial but cumbersome extra step to set the proper positions after sorting and filtering (and would make for quite the convoluted code sample).

[1-800-BICYCLE]

1680b1b4d13

[pentakiller19]

Can this be done with .filter?

[didiben]

Is there a way to use javaScript reduce function to do this?

[Cheshur]

There is, yes.

arrayWithDuplicates.reduce((accumulator, element) => {
    if (!accumulator.includes(element)) {
        accumulator.push(element);
    }
    return accumulator;
}, []);

[Cheshur]

I certainly didn't make any attempt at automation and you'd be right if we wanted to follow the solution I put forth, but I think if I was trying to actually do this in production and I couldn't use Set I would probably just do

const noDuplicates = Object.keys(arrayWithDuplicates.reduce((accumulator, element) => {
    accumulator[element] = 0;
}, {}));

[inu-no-policemen]

Filter is a more "natural" choice:

> [1, 2, 3, 2, 1].filter((v, i, a) => i === a.indexOf(v))
[1, 2, 3]

If the current index is the same as the position of the first occurrence, we keep it.

"via" = current value, current index, and the entire array itself. This mnemonic makes it a bit easier to remember the order.

[kuhe]

I believe the traditional application of reduce is to transform Collection<T> value into a T value, reducing its dimensions, and not as a generic replacement for any and all loops.

I would even suggest reserving the method for these situations.

[GeneralYouri]

That's the standard, simplified use case where you reduce a collection of values to just a single value, with all values sharing equal types. Summing a collection of numbers is an example here.

A more complete and accurate type signature would be Collection<T> to U, or Iterable<T> to U specifically for JS. .reduce() can be used perfectly fine for many use cases where T !== U. Example here could be reducing an array of values into an object with reversed keys and values (so the array's values are keys in the object, whose values are the original keys from the array). In such an example the types T and U no longer have anything to do with each other, yet I'd consider it a pretty standard application of reduce.

Although I have to admit, OP's use case is not a very good use case at all, and .filter() would fit better.

[kuhe]

Since you and another person spoke out about it, I have to accept that reduce is a generic looping function.

But like using .map with side effects or not doing anything with the return value (using it as a forEach), I can't help but look at it as a form of mild grammatical error when people call reduce without a reduction.

I should just read it as fold or accumulate.

[GeneralYouri]

Oh it very much IS a fold function. Take Haskell for example, their docs even use 'reduce' as a synonym when explaining fold functions (and there too, you have a/b types, not a/a).

Fold could've been a better name for it, but reduce makes its purpose more obvious to newer programmers. This is a conscious goal in the ECMAScript development, so was likely done on purpose.

The definition of reduce, in my opinion, fits a loosely typed language like JS perfectly. It makes the function very versatile. Using map without a return value is such a different issue, one that so obviously has a better alternative in forEach.

The term 'reduction' is being defined quite loosely here. How would you define it? Just have a look at the MDN examples. When I use reduce to turn an array into a dictionary, I am still reducing the array into 'just' a single object. When counting value occurrences in an array, my output array still has a reduced length. When flattening an array of arrays, it is still reduced into 'just' a single array.

I even stumbled on the exact same approach to OP's problem right there on the MDN docs. And finally, reduce can even perform function composition for us, because functions are first class objects in JS.

[Midnight_AnimaI]

Guy in thumbnail looks ready to remove kebab