Leetcode problem: Remove Duplicates from Sorted Array

Question

Example :

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums 
             being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

My code to solve this problem is

 var removeDuplicates = function(nums) {
 const non_duplicates = [];

for (let i=0;i<=nums.length-1;i++){
    if(!(non_duplicates.includes(nums[i]))){
        non_duplicates.push(nums[i]);
       
    }
     
}
console.log(non_duplicates)
return non_duplicates.length;

};

That console.log(non_duplicates) displays correct output in stdOut. But when I return non_duplictes it prints empty array in output. And when I return non_duplictes.length it returns some array rather than the length of that array.

Please don't suggest any other method to solve this problem. Just tell what is wrong with this code

You can see that problem here

I think you need to do 2 things: 1) modify the nums input array in place and 2) return the number of non-duplicates as the return value of the function. So, after calling your function, the return value would be 5 and the first 5 values in the passed-in array would be 0,1,2,3,4 (the value of the others doesn't matter). — jarmod
– jarmod, Commented Aug 1, 2022 at 19:57
Your code works fine. Its your return that is the problem. You are returning the length of the array and not the array itself. So just remove .length from the return — imvain2
– imvain2, Commented Aug 1, 2022 at 19:58
@imvain2 No, if you read the Leetcode JS answer template, the return value is a number, while the input/output parameter nums is an array of numbers. The problem also tells you: "Return k after placing the final result in the first k slots of nums." — jarmod
– jarmod, Commented Aug 1, 2022 at 20:00

abozhilov · Accepted Answer · 2022-08-01 21:22:06Z

Your solution doesn't modify the array inplace. That's the first problem. A bigger problem is that your algorithm is with O(N^2) time complexity, due to includes call and given that "1 <= nums.length <= 3 * 104" your solution would be incredibly slow if it ever passes the tests.

The goal is to find a linear solution of the problem. One possible solution would be:

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

Rohìt Jíndal · Accepted Answer · 2022-08-02 12:39:56Z

1

You can achieve that by using Set() Object.

let nums = [0,0,1,1,1,2,2,3,3,4];

const uniqueNums = [...new Set(nums)];

console.log(uniqueNums.length, uniqueNums);

answered Aug 2, 2022 at 12:39

Rohìt Jíndal

27.4k16 gold badges80 silver badges133 bronze badges

Comments

jarmod · Accepted Answer · 2022-08-02 13:41:42Z

You're returning the correct value but you are not overwriting the nums array with the non-duplicate values.

After calling your function, the return value should be 5 and the first 5 values in the passed-in nums array should be 0,1,2,3,4 (the value of the others doesn't matter).

Simplest solution that's compatible with your attempted solution is:

copy the values from non_duplicates into nums
return non_duplicates.length.

Here's a simple example of how to do this:

var removeDuplicates = function (nums) {
  const non_duplicates = [];

  for (let i = 0; i < nums.length; i++) {
    if (!non_duplicates.includes(nums[i])) {
      non_duplicates.push(nums[i]);
    }
  }

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

  return non_duplicates.length;
};

Note: this is not the most efficient solution, and efficiency becomes important with the medium to hard Leetcode challenges, but it's simple, close to your intended solution, and it works.

Collectives™ on Stack Overflow

Leetcode problem: Remove Duplicates from Sorted Array

3 Answers 3

Comments

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Related