Remove Duplicates from Sorted Array (LeetCode 26)

The problem

You get an integer array nums sorted in non-decreasing order. Rearrange it in place so the first k slots hold each distinct value exactly once, in the original order, and return k. What sits after position k doesn’t matter.

Input:  nums = [1, 1, 2, 3, 3]
Output: 3   (nums starts with [1, 2, 3, ...])

There are three distinct values, and they now occupy the first three slots.

How to think about it

Start with brute force. Put the values in a set, sort it, and copy it back. That’s O(n log n) and uses O(n) extra memory, which breaks the “in place” rule. Another naive idea is to delete each duplicate with pop(i), but every delete shifts the rest of the array, giving O(n²).

The key insight: sorted means duplicates are neighbours. You never need to remember all the values you’ve seen. To decide whether nums[i] is new, you only compare it with the last value you kept. If it’s different, it’s new.

So split the work between two pointers. A fast pointer i reads every element. A slow pointer k marks where the next unique value gets written. Everything before k is the finished, de-duplicated prefix. The last kept value is always nums[k-1].

Which pattern is this? Two pointers moving in the same direction, a read/write (slow/fast) pair. The tell is “modify the array in place and return the new length”.

Approach

1. If the array is empty, return 0.
2. The first element is always kept, so start with k = 1.
3. For each i from 1 to the end, compare nums[i] with nums[k-1].
4. If they differ, write nums[i] into nums[k] and increase k.
5. Return k.

Solution

def remove_dups(nums):
    if not nums: return 0
    k = 1                                  # nums[:k] is the de-duplicated prefix
    for i in range(1, len(nums)):
        if nums[i] != nums[k-1]:           # differs from the last kept value
            nums[k] = nums[i]; k += 1      # write it and grow the prefix
    return k
# remove_dups([0,0,1,1,1,2,2,3,3,4]) -> 5  (first 5 slots are 0,1,2,3,4)

Dry run

On nums = [1, 1, 2, 3, 3], starting with k = 1:

The function returns 3, and the first three slots are [1, 2, 3].

Complexity

• Time: O(n). One pass; each element is read once and written at most once.
• Space: O(1). Only two integer pointers. The array is changed in place.

Edge cases and pitfalls

• Empty array returns 0. Without the guard, k = 1 would be wrong.
• All equal, like [7, 7, 7], returns 1.
• No duplicates returns n; every element is “written” onto itself, which is harmless.
• Comparing with nums[i-1] instead of nums[k-1] also works for this problem (sorted input), but comparing with the last kept value is the version that generalises, for example to “allow at most two copies” (compare with nums[k-2]).
• Returning the array instead of k. The judge reads k and checks only the first k slots.

Related problems

• Move Zeroes (LeetCode 283): the same read/write pair, keeping non-zeros instead of new values.
• Remove Duplicates from Sorted List II (LeetCode 82): the linked-list cousin, where duplicates are dropped entirely.
• Sort Colors (LeetCode 75): in-place partitioning with three pointers instead of two.