Remove Duplicates from Sorted Array JS

Question

I'm trying to understand why my solution to this problem is only partially working.

Problem:

Given a sorted array nums, remove the duplicates in-place such that each element appears only once and returns the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

My Solution:

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

This is the outcome I'm getting on leetcode but I don't understand why my solution stops working and the '3s' are not removed?

Output screenshot:

image of the screenshot

You iterate forward and remove items. Each time you remove, everything after that item moves back a slot. So, if you get an array like [15, 19, 19, 19, 21] you'd find index 1 and 2 are the same, remove one, then the new item in index 2 is 19 from the old index 3. However, you just increase the counter i and never check it, moving over to check the (new) index 2 and 3. — VLAZ
– VLAZ, Commented Oct 12, 2020 at 20:40

CertainPerformance · Accepted Answer · 2020-10-12 20:39:58Z

3

When you splice an array while iterating over it, the whole array will change in-place. For example, let's say that indexes 0 and 1 are duplicates (i is 1). Then, if you remove index 1 from the array, what used to be at index 2 will now be at index 1, and what used to be at index 3 will now be at index 2, etc.

So, you need to subtract 1 from i when an element is removed, otherwise the next element will be skipped.

You also have an off-by-one-error - iterate i from 1 to i < nums.length so you don't go past the end of the array.

You also need to pass the index to remove to splice, not the value to remove.

var removeDuplicates = function(nums) {
    for (let i = 1; i < nums.length; i++){
        if(nums[i] === nums[i-1]){
            nums.splice(i, 1);
            i--;
        }
    }
    return nums.length;
};
console.log(removeDuplicates([0, 0, 0]));

answered Oct 12, 2020 at 20:39

CertainPerformance

373k55 gold badges354 silver badges359 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

VLAZ Over a year ago

The alternative is to iterate backwards from nums.length - 1 to 0. Then you don't have to worry about maintaining the index, the shifts in elements don't affect the following iterations.

JackyShows · Accepted Answer · 2020-10-12 20:41:16Z

0

Simple version. Using functions already created

let array = new Set(nums);
let values = array.values();
return Array.from(values);

answered Oct 12, 2020 at 20:41

JackyShows

1912 silver badges11 bronze badges

2 Comments

CertainPerformance Over a year ago

This uses O(n) extra memory, which is forbidden

JackyShows Over a year ago

Didn't know that

Emma Marcier · Accepted Answer · 2020-10-12 20:51:37Z

0

This'd also pass just fine on constant memory:

const removeDuplicates = function (nums) {
    
    let count = 0;
    
    nums.forEach(function (num) {
        if (num !== nums[count]) {
            nums[++count] = num;
        }
    });
    
    return nums.length && count + 1;
};

answered Oct 12, 2020 at 20:51

Emma Marcier

27.8k12 gold badges49 silver badges71 bronze badges

1 Comment

Olivier Boissé Over a year ago

your solution doesn't remove the duplicate elements in the original array

Olivier Boissé · Accepted Answer · 2020-10-12 21:07:02Z

0

function removeDuplicates(nums) {
  let i = 0;
  while(i < nums.length - 1) {
    i += 1 - ((nums[i] === nums[i+1]) && nums.splice(i, 1).length)
  }
  return nums.length;
}

answered Oct 12, 2020 at 21:07

Olivier Boissé

18.5k7 gold badges54 silver badges70 bronze badges

Comments

Mansur Qurtov · Accepted Answer · 2021-06-24 11:37:27Z

0

C# simple solution:

public int RemoveDuplicates(int[] nums) {
        if (nums.Length == 0)
                return 0;
        var i = 0;
            var start = 0;
            var end = 0;

            while (end < nums.Length)
            {
                if (nums[start] != nums[end])
                {
                    nums[++i] = nums[end];
                    start = end;
                }
                end++;
            }

            return i + 1;
    }

answered Jun 24, 2021 at 11:37

Mansur Qurtov

7801 gold badge4 silver badges12 bronze badges

Collectives™ on Stack Overflow

Remove Duplicates from Sorted Array JS

5 Answers 5

1 Comment

2 Comments

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

1 Comment

2 Comments

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related