1

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

Kaiser Soze
  • 1,362
  • 3
  • 14
  • 31
  • 4
    "Remove but don't modify" is contradictory. – Al Kepp Mar 11 '19 at 21:12
  • The code as shown does not remove any duplicates as it does not change the arrays length. – Jonas Wilms Mar 11 '19 at 21:12
  • @kepp sorry I did not explain well. It means not creating a new array, modify the array in place. So no Set or slice. – Kaiser Soze Mar 11 '19 at 21:28
  • @wilms exacly I tried in the console and it does not change anything, but it passes all the tests in leetcode. Which is more confusing, I don’t get it. – Kaiser Soze Mar 11 '19 at 21:29
  • 1
    The code isn't that good, see [Why is using `for…in` on arrays such a bad idea?](https://stackoverflow.com/q/500504/1048572) – Bergi Mar 11 '19 at 21:38
  • @bergi I know, am just a beginner in this. My idea after the loop fails (because more than 2 dups): us toString to convert the array to a string then a regex to replace all duplicates characters, convert again to array. i could not find a working regex, plus it sounded silly and very slow – Kaiser Soze Mar 11 '19 at 21:48
  • 1
    @KaiserSoze The approach (algorithmic idea) of the snippet that you found is quite fine, it's just the loop syntax that's off. No, using strings and regex to detect repetitions is indeed a silly idea. – Bergi Mar 11 '19 at 21:53

1 Answers1

2

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.

Bergi
  • 630,263
  • 148
  • 957
  • 1,375