Remove Duplicates from Sorted Array

The key idea

Because the array is already sorted, every group of equal values is contiguous. Keep a slow write pointer just past the last unique value, and a fast pointer that scans ahead. Whenever the fast value differs from the value at the write pointer, it is a brand-new unique, so copy it forward and advance the write pointer. This compacts all distinct values into the front in one pass with no extra memory.

Problem

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place so that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.

Consider the number of unique elements of nums to be k. To get accepted, you need to do the following things:

Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important, as well as the size of nums. Return k.

The judge tests your solution by checking that the first k returned elements match the expected unique values; values beyond index k are ignored.

Constraints

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

Examples

Input: nums = [1,1,2] Output: 2, nums = [1,2,_]

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

Complexity

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

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →