CODEWITHSUNDEEP
javascriptarraysalgorithm
Kaiser Soze
Kaiser Soze

Reputation: 1498

Remove duplicates from an array in Javascript (without modify the array) - Understand the logic behind

I started using a website called leetcode and one question is to remove all the duplicates in an array without create a new one. Here is the question https://leetcode.com/problems/remove-duplicates-from-sorted-array/description/ My solution was to loop and the check each element against the next one, then if match use splice to remove the duplicated one. it works but not when you have something like [1,1,1,1,1] or [1,1,2,2,2,2,3,3] so I found on github a working code:

var removeDuplicates = function(nums) {
    var i = 0;
    for (var n in nums)
        if (i === 0 || nums[n] > nums[i-1])
            nums[i++] = nums[n];
    return i;
};

This code works and passes all the 160 tests, but I don't understand clearly what is doing, especially the part in nums[i++] = nums[n]; can someone be so kind to help me to understand what this, simple, code is doing? thanks

Upvotes: 1

Views: 370

Answers (1)

Bergi
Bergi

Reputation: 665256

Consider this code that creates a new array:

function removeDuplicates(nums) {
    var res = [];
    var i = 0;
    for (var j=0; j<nums.length; j++)
        if (i === 0 || nums[j] !== res[i-1])
            res[i++] = nums[j];
    return res;
}

The line you're asking about assigns nums[j] as new element at res[i] when the value is not the same as the previous one (res[i-1]), then increments i to put the next non-duplicate value in the next position.

Now we use the same algorithm but instead of assigning to a new res array, we modify the original nums array:

function removeDuplicates(nums) {
    var i = 0;
    for (var j=0; j<nums.length; j++)
        if (i === 0 || nums[j] !== nums[i-1])
            nums[i++] = nums[j];
    nums.length = i; // drop the rest
}

Given that j >= i is guaranteed, we only modify array elements that we've always visited, so there's no harm in writing on the same array that we are reading from.

Upvotes: 2

Related Questions