EasyArrayTwo Pointers

Remove Duplicates from Sorted Array

1 approach, code in every language

Given a sorted integer array, remove the repeated values in place so that each distinct number appears only once, keeping their original ascending order. You may not allocate a second array for the answer.

Return the count k of unique elements. The first k slots of the array must hold those unique values in order; whatever remains beyond position k is irrelevant.

Example 1

Input: nums = [1, 1, 2]

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

Two distinct values remain, so the leading two slots become 1 and 2.

Example 2

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

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

Five unique numbers are compacted to the front while the tail is left unchecked.

Constraints

1 ≤ nums.length ≤ 3 * 10^4
-10^2 ≤ nums[i] ≤ 10^2
nums is sorted in non-decreasing order

Slow/Fast Two Pointers

Keep a slow write pointer marking the last unique value and a fast read pointer scanning ahead for the next new value.

Loading animation…

Intuition

Because the array is sorted, every duplicate group is contiguous, so a value is new only when it differs from the last one we kept. The slow pointer always sits on the final element of the deduplicated prefix, while the fast pointer races ahead. Whenever the fast pointer sees a value that differs from the slow pointer's value, we grow the prefix by one and copy that value in. This overwrites duplicates without ever needing extra storage.

Algorithm walkthrough

1Handle the trivial empty case, then start slow at index 0 as the first kept element.
2Move fast from index 1 to the end of the array.
3When nums[fast] differs from nums[slow], advance slow and copy nums[fast] into that slot.
4Leave fast running so it keeps skipping over equal duplicates automatically.
5Return slow + 1, the number of unique values now sitting at the front.

Implementation

from typing import List

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0
        slow = 0
        for fast in range(1, len(nums)):
            if nums[fast] != nums[slow]:
                slow += 1
                nums[slow] = nums[fast]
        return slow + 1

Time

O(n)

Space

O(1)

A single linear pass with two pointers; all rewriting happens inside the original array.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Arrays

After the pattern

Now solve one you haven't seen.

Collapse Repeated Offsets is our own problem on the technique behind Remove Duplicates from Sorted Array: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free