DSA Removing Duplicates from a Sorted Array

The problem

A sorted list can hold the same value many times in a row. The task is to keep one copy of each value. The kept values stay in the same list, at the front.

The answer has two parts. The first part is the new length. The second part is the prefix of that length, which holds the kept values in order. Anything after the prefix does not matter.

cases = [
    ([1, 1, 2], [1, 2]),
    ([0, 0, 1, 1, 1, 2, 2, 3, 3, 4], [0, 1, 2, 3, 4]),
    ([7, 7, 7], [7]),
    ([], []),
]
for nums, unique in cases:
    print("nums", nums, "unique:", unique, "new length:", len(unique))

Read one row at a time. The list [1, 1, 2] keeps one 1 and the 2. The long list keeps five values, one per run. A list of three 7s keeps a single 7.

Intuition

Sorted order is the whole gift here. Equal values always sit side by side, in runs. A value is new exactly when it differs from the value just before it.

The first fix most people reach for is a second list. Walk the input, and append a value to the new list when it is not there yet. That works, and the brute force below uses it. It costs a second list, though, and the problem asks for the work in place.

A tempting in-place shortcut deletes repeats while scanning. It has a quiet trap. Deleting an item shifts every later item one place left, so the scan steps over the next value without checking it.

nums = [1, 1, 1, 2]
i = 1
while i < len(nums):
    if nums[i] == nums[i - 1]:
        nums.pop(i)
    i += 1
print("after deleting:", nums)
print("expected:      [1, 2]")

The scan removed one 1 and then stepped past the next 1. Two 1s survive instead of one. The fix is to never delete during the scan. Overwrite instead, and move the boundary only when a new value is written.

Brute force: build a new list

The straightforward method builds the answer in a fresh list. Each input value is checked against every kept value. A value with no match is appended.

def dedup_new(nums):
    kept = []
    checks = 0
    for value in nums:
        found = False
        for old in kept:
            checks += 1
            if old == value:
                found = True
                break
        if not found:
            kept.append(value)
    return kept, checks

nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
kept, checks = dedup_new(nums)
print("kept:", kept)
print("comparisons:", checks)

The method is correct. Its cost hides in the inner check. Every new value is compared against all the values kept so far, so the comparison count grows fast when most values are distinct. It also spends memory on a second list the size of the answer.

The optimal solution: a slow write pointer

The write pointer marks the end of the kept prefix, and each value is written there only when it differs from the last kept value. That one rule does the whole job in a single scan, with no second list.

The read pointer visits every index from 1 onward. The value at the read pointer is compared with the value at write - 1, which is the last kept value. A different value is copied to the write position, and the write pointer advances. An equal value is skipped, and nothing moves.

def remove_duplicates(nums):
    if not nums:
        return 0
    write = 1
    for read in range(1, len(nums)):
        if nums[read] != nums[write - 1]:
            nums[write] = nums[read]
            write += 1
    return write

cases = [
    ([1, 1, 2], [1, 2]),
    ([0, 0, 1, 1, 1, 2, 2, 3, 3, 4], [0, 1, 2, 3, 4]),
    ([7, 7, 7], [7]),
    ([], []),
]
for nums, expected in cases:
    data = list(nums)
    length = remove_duplicates(data)
    print(nums, "-> length", length, "prefix", data[:length], "expected", expected)

All four cases from the start of the article pass. The original list is rearranged in place. Only its prefix is the answer, so the values left behind the write pointer are ignored.

Walkthrough

Watch the pointers on [1, 1, 2, 2, 3]. The write pointer starts at 1, because the first value is always kept. Each step below prints the state after that read value is handled.

nums = [1, 1, 2, 2, 3]
write = 1
print("start: write =", write, "list:", nums)
for read in range(1, len(nums)):
    value = nums[read]
    if value != nums[write - 1]:
        nums[write] = value
        write += 1
        action = "new value, written"
    else:
        action = "repeat, skipped"
    print("read", read, "value", value, "-", action, "- list:", nums, "write:", write)
print("new length:", write)
print("prefix:", nums[:write])

The second 1 is a repeat, so nothing moves. The first 2 is new, so it is written at index 1 and the write pointer moves to 2. The second 2 is a repeat of the last kept value. The 3 is new and lands at index 2.

The final write pointer is 3. That number is the new length. The prefix [1, 2, 3] is the deduplicated list.

Complexity

The two-pointer scan takes O(n) time, where n is the length of the list: the read pointer visits each value once and does constant work per value. It takes O(1) extra space, because the only extra storage is the two pointers.

def brute_checks(n):
    kept = []
    checks = 0
    for value in range(n):
        for old in kept:
            checks += 1
            if old == value:
                break
        else:
            kept.append(value)
    return checks

def pointer_comparisons(n):
    nums = list(range(n))
    write = 1
    compared = 0
    for read in range(1, n):
        compared += 1
        if nums[read] != nums[write - 1]:
            write += 1
    return compared

for n in [10, 20, 40]:
    print("n =", n, "brute checks:", brute_checks(n),
          "pointer comparisons:", pointer_comparisons(n))

The counts use all-distinct inputs, which is the worst case for the new-list method. Its checks grow roughly with the square of n. The pointer comparisons grow by exactly one per extra value. Doubling n doubles the pointer work and roughly quadruples the brute-force work.

Edge cases and pitfalls

An empty list has no first value to keep. The solution returns 0 before the write pointer is set up. Without that guard, write = 1 would claim a length of 1 for a list that holds nothing.

One common mistake is comparing each value with nums[0] instead of the last kept value. That test only catches repeats of the first value. Repeats of every later value slip through. The comparison must follow the kept prefix as it grows.

Another mistake is returning the whole list as the answer. The list keeps its old length and its stale tail. Only the length and the prefix carry the result.

def remove_duplicates(nums):
    if not nums:
        return 0
    write = 1
    for read in range(1, len(nums)):
        if nums[read] != nums[write - 1]:
            nums[write] = nums[read]
            write += 1
    return write

for nums in [[], [5], [3, 3, 3, 3], [1, 2, 3], [-2, -2, 0, 0, 9]]:
    data = list(nums)
    length = remove_duplicates(data)
    print(nums, "-> length", length, "prefix", data[:length])

A list with no repeats keeps its full length. A list of one repeated value shrinks to length 1. Negative values behave like any others, because only equality matters.