DEV Community

Cover image for Remove the duplicates in-place such that each unique element appears only once
chandra penugonda
chandra penugonda

Posted on • Edited on

Remove the duplicates in-place such that each unique element appears only once

#javascript #programming #beginners #interview

Good morning! Here's your coding interview problem for today.

This problem was asked by Tencent.

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.

Example

function removeDuplicates(nums){

}

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

Solution

function removeDuplicates(nums) {
  const set = new Set();

  for (let i = 0; i < nums.length; i++) {
    set.add(nums[i]);
  }

  let k = 0;
  for (const num of set) {
    nums[k++] = num;
  }
  nums.length = k;
  return k;
}
Enter fullscreen mode Exit fullscreen mode

Explanation

  • Use a Set to collect only unique elements from the unsorted array.
  • Loop over the original array and add each element to the Set.
  • Set will only contain unique elements, discarding duplicates.
  • Loop over Set to rebuild array with only uniques in original order.
  • set size of array to k
  • Return k which is the new length after removing duplicates.

Top comments (2)

Collapse
 
tracygjg profile image
Tracy Gilmore • • Edited

Hi Chandra,

Using the Set data type is an excellent way to remove duplicates and can be created directly from an array as follows.

const set = new Set(nums);
Enter fullscreen mode Exit fullscreen mode

The set can them be turned back into a simple array using its keys method, as follows.

return [...set.keys()];
Enter fullscreen mode Exit fullscreen mode

This can greatly simplify the example above but does not explain the how it works anywhere near as well.

Another, more complicated, approach is to use the Array.reduce method, as follows.

const deduped = nums.reduce((dd, n) => dd.includes(n) ? dd : [...dd, n], []);

return deduped;
Enter fullscreen mode Exit fullscreen mode

I accept neither of the above approaches are 'in-place' but this can be resolved using the following script.

nums.splice(0, nums.length, ...deduped);

// or

nums.length = 0;
nums.push(...deduped);
Enter fullscreen mode Exit fullscreen mode

Best regards, Tracy

Collapse
 
tracygjg profile image
Tracy Gilmore • • Edited

Chandra,

Your example needs to return nums not k otherwise the output would be the number 3 and not the original array.

Your post certainly had me thinking, so here is an in-place alternative.

function removeDuplicates(nums) {
    let k = 0;
    for (let i = 0; i < nums.length; i++) {
        if (!nums.slice(0, k).includes(nums[i])) {
            nums[k++] = nums[i];
        }
    }
    nums.length = k;
    return nums;
}
Enter fullscreen mode Exit fullscreen mode

Tracy

Read next

mdarifulhaque profile image

1792. Maximum Average Pass Ratio

MD ARIFUL HAQUE -

nikl profile image

Ask Anything in VS Code now for Development!

Nik L. -

msnmongare profile image

Essential Use Cases to Master API Development and Integration

Sospeter Mong'are -

daksh_kataria_9c4197f3f7c profile image

Top 10 Cybersecurity Interview Questions and Answers for 2025

Daksh Kataria -