In place deduping an array

In place deduping an array

easy but analytical

Subscribe to my newsletter and never miss my upcoming articles

❓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

Interested in reading more such articles from Rajat Jain?

Support the author by donating an amount of your choice.

#javascript#array#arrays#interview#frontend
Β 
Share this
Proudly part of