Remove Duplicates from Sorted Array in Python — 3 Ways

The Remove Duplicates from Sorted Array problem (LeetCode #26) appears deceptively simple, but the constraint of in-place modification makes it a great two-pointer exercise.

Problem Statement

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such 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. The first k elements of nums should contain the unique numbers.

Constraints:

• Must use O(1) extra space
• The array is already sorted
• Don’t allocate a new array

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, _, _, _, _, _]

Approach 1: Two-Pointer (Fast & Slow)

The classic O(n) in-place approach. Uses a slow pointer (k) to track the position of the last unique element, and a fast pointer (i) to scan ahead.

def removeDuplicates(nums):
    if not nums:
        return 0

    k = 1   # next position to write unique value (index 1 onward)

    for i in range(1, len(nums)):
        if nums[i] != nums[i - 1]:
            nums[k] = nums[i]
            k += 1

    return k

Why It Works

Because the array is sorted, duplicates are always next to each other. When nums[i] != nums[i-1], we’ve found a new unique value. Write it at position k and increment k.

Walkthrough

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

Result: k = 5, first 5 elements are [0, 1, 2, 3, 4].

Approach 2: Explicit Tracking Variable (More Verbose)

Use a separate variable to track the last unique value seen.

def removeDuplicates_verbose(nums):
    if not nums:
        return 0

    write_index = 1
    last_seen = nums[0]

    for i in range(1, len(nums)):
        current = nums[i]
        if current != last_seen:
            nums[write_index] = current
            last_seen = current
            write_index += 1

    return write_index

This is logically identical to Approach 1 but may read more clearly for some learners.

Approach 3: Set-Based Shortcut (Not In-Place)

Python sets automatically deduplicate, but this allocates new space so it violates the O(1) constraint.

def removeDuplicates_set(nums):
    unique = list(dict.fromkeys(nums))  # preserves order
    nums.clear()
    nums.extend(unique)
    return len(unique)

Or more explicitly:

def removeDuplicates_set_v2(nums):
    seen = set()
    write_index = 0
    for num in nums:
        if num not in seen:
            seen.add(num)
            nums[write_index] = num
            write_index += 1
    return write_index

Complexity

Edge Cases

# Empty array
assert removeDuplicates([]) == 0

# Single element
assert removeDuplicates([5]) == 1

# All duplicates
assert removeDuplicates([1, 1, 1, 1]) == 1, nums[0] == 1

# Already unique
assert removeDuplicates([1, 2, 3, 4]) == 4

# Two elements, duplicates
assert removeDuplicates([1, 1]) == 1

# Two elements, unique
assert removeDuplicates([1, 2]) == 2

# Long-sorted
assert removeDuplicates([-3, -1, 0, 0, 0, 3, 3]) == 4

Common Mistakes

1. Allocating a new array — violates the in-place constraint
2. Checking nums[i] == nums[k-1] — this is a common bug; the comparison should be against nums[i-1]
3. Returning k - 1 — k is already the count, not the last index
4. Not handling empty array — would throw an IndexError
5. Assuming output is [1, 2, ..., k] — no, nums still contains n elements; only first k matter

Testing Your Solution

def test_removeDuplicates():
    # Test case 1
    nums1 = [1, 1, 2]
    k1 = removeDuplicates(nums1)
    assert k1 == 2, f"Expected 2, got {k1}"
    assert nums1[:2] == [1, 2]

    # Test case 2
    nums2 = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
    k2 = removeDuplicates(nums2)
    assert k2 == 5
    assert nums2[:5] == [0, 1, 2, 3, 4]

    print("All tests passed!")

test_removeDuplicates()

Real-World Use Cases

• Database denormalization: removing duplicate rows with sorted IDs
• Sensor deduplication: sensor streams with occasional repeated readings
• Log processing: deduplicating log entries sorted by timestamp
• Unique ID tracking: cleaning sorted ID lists

Extension: Remove N Occurrences

Allow up to 2 occurrences of each number (LeetCode #80):

def removeDuplicatesAllowTwo(nums):
    if len(nums) <= 2:
        return len(nums)
    k = 2
    for i in range(2, len(nums)):
        if nums[i] != nums[k - 2]:
            nums[k] = nums[i]
            k += 1
    return k

The two-pointer approach is the interview-standard answer: O(n) time, O(1) space, works only on sorted inputs. Master it before tackling un unsorted variant.

Related Problems

• Remove Duplicates from Sorted Array in Dart
• Remove Duplicates from Sorted Array in Go
• Remove Duplicates from Sorted Array in Swift
• Move Zeroes in Python
• Two Sum in Python
• Maximum Subarray in Python

FAQ

What is the best approach to solve Remove Duplicates from Sorted Array in Python?

The recommended approach is the optimal approach, which runs in O(n) time with O(1) space. The full Python implementation is shown above.

What is the time complexity of Remove Duplicates from Sorted Array in Python?

Using the optimal approach, the time complexity is O(n) and the space complexity is O(1).