DEV Community

Cover image for JavaScript Katas: Remove duplicates
miku86
miku86

Posted on

 

JavaScript Katas: Remove duplicates

Intro 🌐

I take interesting katas of all levels and explain how to solve them.

Problem solving is an important skill, for your career and your life in general.

You'd better learn to solve problems!


Source

I take the ideas for the katas from different sources and re-write them.

Today's source: Codewars


Understanding the Exercise ❗

First, we need to understand the exercise!

This is a crucial part of (software) engineering.

Go over the exercise explanation again until you understand it 100%.

Do NOT try to save time here.

My method to do this:

  1. Input: What do I put in?
  2. Output: What do I want to get out?

Today's exercise

Write a function removeDuplicates, that accepts one parameter: inputArray.

Given a numbers array, e.g. [1, 1, 2], return a numbers array without duplicates, e.g. [1, 2]. The order of the sequence has to stay the same.


Input: a numbers array.

Output: a numbers array.


Thinking about the Solution 💭

I think I understand the exercise (= what I put into the function and what I want to get out of it).

Now, I need the specific steps to get from input to output.

I try to do this in small baby steps.

  1. Loop over every number
  2. Check if current number has been seen before
  3. If no (= not seen), save it into the results
  4. Return results

Example:

  • Input: [1, 1, 2]
  • Iteration 1: 1 been seen? => No => save it => [1]
  • Iteration 2: 1 been seen? => Yes => do nothing => [1]
  • Iteration 3: 2 been seen? => No => save it => [1, 2]
  • Output: [1, 2] ✅

Implementation (for loop) ⛑

function removeDuplicates(inputNumbers) {
  // variable to save result
  const withoutDuplicates = [];

  // loop over every number
  for (const number of inputNumbers) {
    // check if current number has been seen before
    // if no (= not seen), save it into the results
    if (!withoutDuplicates.includes(number)) {
      withoutDuplicates.push(number);
    }
  }

  // return result
  return withoutDuplicates;
}
Enter fullscreen mode Exit fullscreen mode

Result

console.log(removeDuplicates([1, 1, 2]));
// [ 1, 2 ] ✅

console.log(removeDuplicates([3, 3, 2, 2, 1]));
// [ 3, 2, 1 ] ✅
Enter fullscreen mode Exit fullscreen mode

Implementation (functional) ⛑

function removeDuplicates(inputNumbers) {
  return inputNumbers.reduce(
    (accumulated, current) => {
      // check if current number has been seen before
      return accumulated.includes(current)
        ? accumulated // if yes (= already seen), return the old values without changes
        : accumulated.concat(current); // if no (= not seen), return the old values plus the current one
    },
    [] // we start with an empty array (like "withoutDuplicates" in the alternative solution)
  );
}
Enter fullscreen mode Exit fullscreen mode

I'm using concat to connect the old values with the current one. You can also use the spread operator like we did here.

Result

console.log(removeDuplicates([1, 1, 2]));
// [ 1, 2 ] ✅

console.log(removeDuplicates([3, 3, 2, 2, 1]));
// [ 3, 2, 1 ] ✅
Enter fullscreen mode Exit fullscreen mode

Implementation (Set) ⛑

function removeDuplicates(inputNumbers) {
  // we go from array (inputNumbers) to set (new Set()) to array (...)
  return [...new Set(inputNumbers)];
}
Enter fullscreen mode Exit fullscreen mode

In JavaScript, in the Set data structure a value may only occur once and the order is preserved, so this solves our problem too. If you don't use JavaScript, pay attention to the fact, that not every programming language keeps the original order in a Set. (Thanks to @pentacular)

We use a temporary change in the data structure (a Set) to remove our duplicates. Then we convert the Set back to an array.

Result

console.log(removeDuplicates([1, 1, 2]));
// [ 1, 2 ] ✅

console.log(removeDuplicates([3, 3, 2, 2, 1]));
// [ 3, 2, 1 ] ✅
Enter fullscreen mode Exit fullscreen mode

Playground ⚽

You can play around with the code here


Next Part ➡️

Great work, mate!

We learned how to use a for of loop, a lot of functional stuff and Set.

I hope that you can use your new learnings to solve problems more easily!

Next time, we'll solve another interesting kata. Stay tuned!


If I should solve a specific kata, shoot me a message here.

If you want to read my latest stuff, get in touch with me!


Further Reading 📖


Questions ❔

  • How often do you do katas?
  • Which implementation do you like more? Why?
  • Any alternative solution?
  • Have you ever used a Set?

Top comments (6)

Collapse
 
pentacular profile image
pentacular

Because in the data structure Set a value may only occur once, this solves our problem too.

This isn't sufficient, since you require the order to be preserved.
Fortunately Sets are iterated in insertion order ... :)

But this isn't generally a property of sets, so it's worth noting.

Collapse
 
miku86 profile image
miku86

Hey pentacular,

thank you, I just updated the section.

Collapse
 
aminnairi profile image
Amin

Very bad solution for anyone in search of performance but here is my take at the challenge using a terminal recursion and TypeScript.

"use strict";

/**
 * Deduplicate an array
 * 
 * @example
 * deduplicate([1, 2, 2, 3, 3, 3]); // [1, 2, 3]
 * deduplicate(["boom", "boom", "satellite"]); // ["boom", "satellite"]
 */
function deduplicate<T>([item, ...items]: T[], deduplicated: T[] = []): T[] {
    if (item === undefined) {
        return deduplicated;
    }

    if (deduplicated.includes(item)) {
        return deduplicate(items, deduplicated);
    }

    return deduplicate(items, [...deduplicated, item]);
}
Collapse
 
harrisgca profile image
Glenn Harris

jsben.ch/Uvedk

Performance comparison

  1. For loop
  2. new Set
  3. reduce()
Collapse
 
miku86 profile image
miku86

Thanks Glenn!

When I run the test,
my results differ from yours:

  1. For: 100%
  2. Reduce: 90%
  3. Set: 76%

Do you know something about the internals of the benchmark?

Collapse
 
harrisgca profile image
Glenn Harris

Unfortunately I don't know anything about the internals, even after some research. The results I listed above were in Chrome browser, so I reran the tests in Firefox and Safari and got wildly different results.

Firefox v78.0.2

  1. For (100%)
  2. Reduce (73%)
  3. Set (65%)

Safari v13.1.2

  1. For (100%)
  2. Reduce (64%)
  3. Set (18%)

Chrome 84.4.04

  1. For (100%)
  2. Set (78%)
  3. Reduce (37%)