Remove Duplicates from Sorted Array

easy array two pointers

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.

Two pointers: a write index w marks where the next unique value belongs; a read index r scans the array. Only when the new value differs from the previous kept one do we copy and advance w.

Inputnums = [1, 1, 2, 3, 3, 3, 5]

Output4, nums starts with [1, 2, 3, 5, …]

nums (sorted, comma-separated)

def remove_duplicates(nums):
    if not nums:
        return 0
    w = 1
    for r in range(1, len(nums)):
        if nums[r] != nums[w - 1]:
            nums[w] = nums[r]
            w += 1
    return w

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

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

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

Explanation

Because the array is already sorted, every group of equal values is bunched together. That means we only ever need to compare a value with the last unique value we decided to keep, not with everything before it.

We use two pointers. A write index w tracks where the next unique value goes; it starts at 1 because the very first element is always unique. A read index r scans the rest of the array.

At each step we check nums[r] != nums[w - 1]. Here nums[w-1] is the most recently kept value. If the new value differs, it is fresh, so we copy it into nums[w] and advance w. If it is the same, it is a duplicate and we simply skip it.

Example: nums = [1, 1, 2, 3, 3, 3, 5]. The second 1 matches the kept 1, so skip. 2 differs, keep it. 3 differs, keep it; the next two 3s match, skip. 5 differs, keep. The front becomes [1, 2, 3, 5] and we return 4.

One pass, no extra array, constant memory — the unique values end up packed at the front.

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