Remove Duplicates From Sorted Array

Difficulty: Easy Source: NeetCode

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. Return k — the number of unique elements in nums.

The first k elements of nums must hold the unique elements. The remaining elements and the size of the array do not matter.

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

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

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

• Sorted Arrays — recognizing that equal adjacent elements are duplicates
• Two Pointers — slow/fast pointer pattern for in-place array compaction

1. Brute Force

Intuition

Collect all unique elements into a new array, then write them back into nums. Easy to reason about, but uses O(n) extra space. Since the array is sorted, uniqueness is trivial — just skip any element that equals the previous one.

Algorithm

1. Build unique by iterating nums and appending a value only when it differs from the previous value.
2. Write unique back into the first len(unique) positions of nums.
3. Return len(unique).

Solution

def removeDuplicates(nums):
    unique = [nums[0]]
    for i in range(1, len(nums)):
        if nums[i] != nums[i - 1]:
            unique.append(nums[i])
    for i, val in enumerate(unique):
        nums[i] = val
    return len(unique)


nums = [1, 1, 2]
k = removeDuplicates(nums)
print(k, nums[:k])  # 2 [1, 2]

nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
k = removeDuplicates(nums)
print(k, nums[:k])  # 5 [0, 1, 2, 3, 4]

Complexity

• Time: O(n)
• Space: O(n)

2. Slow / Fast Two Pointers

Intuition

Use a slow pointer k as the write index (where the next unique element should go) and a fast pointer i that scans every element. Whenever the fast pointer finds a value different from the element just written at k - 1, we’ve found a new unique value — write it to nums[k] and advance k. Elements equal to nums[k - 1] are just skipped. The array is already sorted, so duplicates always sit adjacent to each other.

Algorithm

1. Initialize k = 1 (the first element is always unique, so the write position starts at index 1).
2. For i from 1 to len(nums) - 1:
   • If nums[i] != nums[k - 1]: write nums[i] to nums[k], increment k.
3. Return k.

Solution

def removeDuplicates(nums):
    k = 1  # nums[0] is always kept; start writing at index 1
    for i in range(1, len(nums)):
        if nums[i] != nums[k - 1]:
            nums[k] = nums[i]
            k += 1
    return k


nums = [1, 1, 2]
k = removeDuplicates(nums)
print(k, nums[:k])  # 2 [1, 2]

nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
k = removeDuplicates(nums)
print(k, nums[:k])  # 5 [0, 1, 2, 3, 4]

nums = [1, 1, 1]
k = removeDuplicates(nums)
print(k, nums[:k])  # 1 [1]

Complexity

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

Common Pitfalls

Comparing nums[i] to nums[i-1] instead of nums[k-1]. Once you start overwriting elements, nums[i-1] might have already been changed. Always compare the fast pointer against what’s actually at the write head nums[k-1].

Initializing k = 0 and starting the loop at 0. The first element is always unique — there’s nothing to compare it against. Starting with k = 1 (the element at index 0 is already placed) and i = 1 avoids an unnecessary edge-case check.

Returning k vs. reading nums[:k]. k is a count, not an index. nums[:k] gives the correct slice — nums[:k-1] would miss the last unique element.