Remove Duplicates from Sorted Array [Easy] — Write Pointer

Problem Statement

Given a sorted integer array, remove duplicates in-place. Return the number of unique elements. Relative order must be maintained.

Input: [1,1,2]     → Output: 2 (nums=[1,2,_])
Input: [0,0,1,1,1,2,2,3,3,4] → Output: 5

Intuition

Write pointer starts at 1. Read pointer starts at 1. If nums[read] != nums[read-1] (or != nums[write-1]), copy to write position and advance write.

Solutions

C

int removeDuplicates(int* nums, int n) {
    if(n==0) return 0;
    int w=1;
    for(int r=1;r<n;r++) if(nums[r]!=nums[r-1]) nums[w++]=nums[r];
    return w;
}

C++

int removeDuplicates(vector<int>& nums) {
    int w=1;
    for(int r=1;r<nums.size();r++) if(nums[r]!=nums[r-1]) nums[w++]=nums[r];
    return w;
}

Java

public int removeDuplicates(int[] nums) {
    int w=1;
    for(int r=1;r<nums.length;r++) if(nums[r]!=nums[r-1]) nums[w++]=nums[r];
    return w;
}

JavaScript

var removeDuplicates = function(nums) {
    let w=1;
    for(let r=1;r<nums.length;r++) if(nums[r]!==nums[r-1]) nums[w++]=nums[r];
    return w;
};

Python

def removeDuplicates(nums: list[int]) -> int:
    w = 1
    for r in range(1, len(nums)):
        if nums[r] != nums[r-1]:
            nums[w] = nums[r]
            w += 1
    return w

Complexity

Time: O(n)
Space: O(1)

Variant: Allow at most k duplicates

def removeDuplicates_k(nums, k):
    w = 0
    for x in nums:
        if w < k or nums[w-k] != x:
            nums[w] = x; w += 1
    return w