Leetcode 26: Remove Duplicates from Sorted Array

This problem is part of the Introduction to Data Structures Arrays-101 section in LeetCode.

Problem Statement

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return 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.

Example 1:

Given nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.

Example 2:

Given nums = [0,0,1,1,1,2,2,3,3,4],

Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.

Solution

Two pointers

The given array is a sorted array, so duplicate numbers will be group together. First, we can handle the edge case of empty array. Then we can start iterating elements from the head.

The second pointer will go through all elements in the list, and the first pointer only move when meeting the unique number.

var removeDuplicates = function(nums) {
   // Handling Edge Case
   if(nums.length === 0 ) return 0
     let p1 = 0
     for(let p2 = 1; p2< nums.length; p2++){
        if(nums[p1] !== nums[p2]){
            p1++;
            nums[p1] = nums[p2]
        }       
     }
    return p1 +1        
}

Beside, we can also start iterator from the end of array. If the value of two pointer is the same, then remove the element.

var removeDuplicates = function(nums) {
    // Handling Edge Case
    if(nums.length === 0 ) return 0
    for(let i = nums.length-1; i > 0;i--){
        if(nums[i]===nums[i-1]){
            nums.splice(i,1)
        }
    }
    return nums.length
};