noodleProblems/
Remove Duplicates from Sorted Array
#35

Remove Duplicates from Sorted Array

AlgorithmeasyArrayTwo Pointers

Given an integer array nums sorted in **non-decreasing** order, remove the duplicates **in place** so that each distinct value appears only once. The relative order of the kept elements must stay the same.

Because the array can't be resized in place, you don't delete anything — instead you compact the unique values into the **front** of nums. Let k be the number of distinct values. Your job:

- Place the first k distinct values, in order, in nums[0] through nums[k - 1]. - **Return k.** Whatever ends up beyond index k - 1 doesn't matter.

Both the value you return and the first k elements of the mutated array are checked; the tail is ignored. Aim for O(n) time and O(1) extra space.

Example cases

  • one duplicate
    in nums = [1,1,2]
    out [1,2]
    Distinct values are 1 and 2, so k = 2 and nums starts with [1, 2].
  • many duplicates
    in nums = [0,0,1,1,1,2,2,3,3,4]
    out [0,1,2,3,4]
    Five distinct values, so k = 5.
  • no duplicates
    in nums = [-3,-1,0,5]
    out [-3,-1,0,5]

Constraints

  • 0 <= nums.length <= 3 * 10^4
  • -100 <= nums[i] <= 100
  • nums is sorted in non-decreasing order.
Saved
nums =
[1,1,2]