In place deduping an array

❓Question

Given an array containing all kinds of data, please implement a function deduplicate() to remove the duplicates. You should modify the array in place.

Before jumping on the later sections, do give it a try yourselves. These blogs will only help if you grow while you learn.

🧠 Churning

This is quite an easy problem. However, following key points make it a good problem to be asked in an interview.

1. The array can have all kinds of data.
2. We have to modify the array in place and not return another modified array object.

💡 Solution I - Naïve

Okay, let us do this. We keep a map of visited items and iterate over the array using the good old for loop.

Wait whatt!!

Isn't using a for loop in modern day programming a taboo?

Well, actually this is quite a subjective question. It is considered a bad practice as we are moving more and more towards the functional programming paradigm, where things are declarative in nature and not imperative.

In this case, we want to control the iteration in the way that we want to increase the index only when the current item is not found in map and if it is, then we will just splice it right off the array.

function deduplicate(arr) {
  const visited = new Map();
  for(let i=0;i<arr.length;) {
    if (visited.has(arr[i])) {
      /* splice takes in which index to start from and till what length
      do you want to slice */
      arr.splice(i, 1);
    } else {
      visited.set(arr[i], true);
      // increment the index only in this case
      i++;
    }
  };
  return arr;
}

Fine enough🪅

What about this usecase

const arr = [1, 5, 'b', 5, 1, undefined, 'a', 'a', 'a', 'b', undefined, true, 'true',false, {}, {}]
console.log(deduplicate(arr))
// [1, 5, 'b', undefined, 'a', true, 'true', false, {}, {}]

In this, you have undefined as an item, and in this case, our Map will have an issue. You can have undefined as a key in a map, it omits it out. So, in this case, the visited map will not have undefined as a key.

Hmm... 🤔 🧐

What to do now?

💡 Solution 2 - Slightly better

Oh I know, why not use a Set instead of a Map. Well, there you go 🚀

function deduplicate(arr) {
  const visited = new Set();
  for(let i=0;i<arr.length;) {
    if (visited.has(arr[i])) {
      arr.splice(i, 1);
    } else {
      visited.add(arr[i]);
      i++;
    }
  };
  return arr;
}

Is it over yet? 🥸

Wait wait wait..the solution and brain churning isn't over yet.

⏰ Time Complexity Analysis

What is the time complexity of our solution?

Here, in the second solution, we are iterating over the array and then using set.has() which takes O(1) and splice which takes O(n) time complexity. So, overall the time complexity becomes 🔥O(n^2)🔥 in the worst case.

Well, we don't want that. Can we think of a better solution here?

Solution 3 - O(n)

We can think of a 2-pointer approach here. I will have one pointer which will be used to repopulate the new values in the array and one which will just be used for iteration.

function deduplicate(arr) {
  const visited = new Set();
  let back = 0;
  // front is being used for iteration
  for(let front = 0; front < arr.length; front++) {
    // if duplicate: proceed only front;
    // if not: proceed both;
    if(visited.has(arr[front])) {
      continue;
    }
    visited.add(arr[front]);
    arr[back] = arr[front];
    back++;
  }
  /* this will decrease the size of array and we will get
  a deduped array */
  arr.length = back;
}

Well, there you go 🚀

If you liked what you read 🧑‍🏫 and got to learn new things, do hit like 👍 and subscribe 🔖 to my newsletter to get instantly notified whenever I drop in new content. And don't forget to follow 🚀 me on

Hashnode - Rajat Jain

Twitter - @rajat_codes

Instagram - @javascript_to_the_rescue

LinkedIn - Rajat Jain