022. Deduplicate a Sorted Array

Foundation · Download this solution · All solutions and shared helpers

Problem

Modify a nondecreasing integer list so its first k positions contain the distinct values in sorted order, and return k. Values beyond k are unspecified and the physical list length need not change. Empty input returns zero.

Examples

Example 1

a = [1, 1, 2, 2, 3]
(deduplicate_sorted(a), a[:3])
=> (3, [1, 2, 3])

The meaningful prefix has three values.

Example 2

deduplicate_sorted([])
=> 0

There is no meaningful prefix.

Example 3

a = [7, 7, 7]
(deduplicate_sorted(a), a[:1])
=> (1, [7])

One duplicate run contributes one value.

Reveal the worked solution and reasoning

Why this mechanism works

Sorting places equal values together. Compare each incoming value with the last value already committed, not with a cell whose meaning is vague after mutation. The write frontier never overtakes the read frontier, so compacting accepted values cannot destroy unread data.

State and boundaries

write is the meaningful output length. nums[:write] contains the distinct values of the consumed prefix.

Protocol

Start write at zero.
Read each value from left to right.
Accept when the output is empty or its last value differs.
Write the accepted value and advance write.
Return write.

Visualization

read:  [1,1,2,2,3]
write: [1,2,3 | ?,?]
meaningful interval: [0,3)

Python implementation

def deduplicate_sorted(nums):
    write = 0
    for value in nums:
        if write == 0 or nums[write - 1] != value:
            nums[write] = value
            write += 1
    return write

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

(deduplicate_sorted(a), a[:3])

L2 deduplicate_sorted: write = 0
nums=[1, 1, 2, 2, 3]; write=0

L3 deduplicate_sorted: for value in nums:
nums=[1, 1, 2, 2, 3]; write=0; value=1

L6 deduplicate_sorted: write += 1
nums=[1, 1, 2, 2, 3]; write=1; value=1

L3 deduplicate_sorted: for value in nums:
nums=[1, 1, 2, 2, 3]; write=1; value=2

L5 deduplicate_sorted: nums[write] = value
nums=[1, 2, 2, 2, 3]; write=1; value=2

L6 deduplicate_sorted: write += 1
nums=[1, 2, 2, 2, 3]; write=2; value=2

L3 deduplicate_sorted: for value in nums:
nums=[1, 2, 2, 2, 3]; write=2; value=3

L5 deduplicate_sorted: nums[write] = value
nums=[1, 2, 3, 2, 3]; write=2; value=3

L6 deduplicate_sorted: write += 1
nums=[1, 2, 3, 2, 3]; write=3; value=3

Result: (3, [1, 2, 3]). The meaningful prefix has three values.

deduplicate_sorted([])

L2 deduplicate_sorted: write = 0
nums=[]; write=0

Result: 0. There is no meaningful prefix.

Why the solution is correct

The first accepted value starts a distinct sorted prefix. Later equal values add no new distinct value; later different values are larger and can be appended safely. Every distinct run contributes exactly once, and unread cells remain available.

Time and space

O(n) time and O(1) auxiliary space.

Common mistakes

Returning the whole physical list exposes unspecified tail cells. Comparing with nums[write] tests an uncommitted location.

Reasoning card

State: write is the meaningful output length. nums[:write] contains the distinct values of the consumed prefix.

Invariant: The prefix before write is unique and final.

Decision to rehearse: Compare incoming values with the last committed output.

Finish: Return write

Transfer exercise

Allow each distinct value at most twice. Which previously committed output cell should the incoming value be compared with?