Remove Duplicates from Sorted Array

The word “remove” is misleading here. You do not need to shrink the Python list or delete values from its tail. You need to compact the distinct values into the front of the same array and return the length of that valid prefix.

That output contract determines the whole Remove Duplicates from Sorted Array solution:

1. Read every value from left to right.
2. Keep the first occurrence of each value.
3. Write kept values into the next available prefix position.
4. Return the prefix length k.

For example:

nums = [1, 1, 2]
k = 2
nums[:k] = [1, 2]

Everything after nums[k - 1] is irrelevant.

Read the Output Contract First

The input is an integer array sorted in non-decreasing order. Values may repeat, and the array must be modified in place.

After the function finishes:

• k equals the number of distinct values.
• nums[:k] contains each distinct value exactly once.
• The retained values remain in sorted order.
• Positions from index k onward do not matter.

“In place” means reusing the supplied array instead of building a separate array of unique values. It does not mean that the Python list must physically become shorter. The judge checks the returned count and the first k positions.

So this is not a deletion problem. It is an in-place array compaction problem: scan a larger region, preserve selected values, and pack them into the front.

Keep the first value. For every later value, write it only when it differs from the last distinct value already retained.

That rule gives the two pointers separate jobs: one observes the input, and one builds the answer.

Spot the Sorted-Adjacency Signal

The sorted input is the decisive clue.

If equal values appear in a sorted array, all occurrences of a value are next to one another:

[0, 0, 1, 1, 1, 2, 2, 3]

The three 1 values form one consecutive group. Once we keep the first 1, every later 1 in that group is a duplicate. A value is new when it differs from the last distinct value we kept.

Without sorting, that local comparison would not be enough:

[2, 1, 2]

The second 2 is not adjacent to the first. In a general array, you might need a set to remember every value seen so far. Here, sorting has already organized duplicates into groups, so a set is unnecessary and would not satisfy the required in-place output contract.

The global question—“Have I seen this value anywhere before?”—has become a local question: “Is this value different from the last retained value?” That is the leverage supplied by the sorted input.

This is one specific use of two pointers. The pointers do not move at unequal rates to detect a cycle, and they do not define a sliding window. One reads; the other compacts.

Separate the Read and Write Responsibilities

Start from the obligations instead of memorizing a pointer template.

• read visits every input position.
• write is the length of the retained prefix and the next destination index.
• nums[0:write] is the verified output built so far.
• nums[write - 1], when write > 0, is the last distinct value retained.

Initialize write to 0. This represents an empty retained prefix, so the first value should be accepted without a comparison.

For each nums[read]:

1. If write == 0, accept the value.
2. Otherwise compare it with nums[write - 1].
3. If they are equal, skip the current value.
4. If they differ, write the current value at nums[write], then increment write.

write = 0

for read from 0 to len(nums) - 1:
    if write == 0 or nums[read] != nums[write - 1]:
        nums[write] = nums[read]
        write += 1

return write

The write may happen behind the read pointer. That is expected: after duplicates are skipped, a later distinct value moves left into an earlier slot.

The destination is never ahead of the current read position. Since write is at most read + 1, a write replaces a processed position or the position currently being read; it cannot overwrite an unread value.

Prove the Retained-Prefix Invariant

The code is short enough to memorize. That is exactly why an invariant matters: a wrong comparison or broken initialization can still produce plausible output on a small example.

After processing the values through the current read position, nums[0:write] contains exactly the distinct values seen so far, once each, in sorted order. write is the length of that verified prefix.

The write pointer is the frontier between trustworthy output and unclassified input.

Initialization

Before reading any values, write = 0, so the retained prefix is empty. It contains exactly the distinct values seen so far: none. The invariant holds.

Duplicate case

Suppose nums[read] equals nums[write - 1]. Because the input is sorted, the current value belongs to the same consecutive group as the last retained value. That value has already been kept once.

Skipping the current value changes neither the prefix nor write, so the invariant remains true.

New-value case

Suppose nums[read] differs from nums[write - 1]. In a sorted array, the current value cannot be a later occurrence of an earlier retained value: all occurrences of that earlier value would have appeared in the same group before the current position.

Write the new value to nums[write]. The verified prefix grows by one correct distinct value. Incrementing write records its new length.

Termination

When read has visited every input position, the prefix contains every distinct value exactly once and in sorted order. Therefore k = write is both the correct count and the boundary of the meaningful output.

Dry-Run the State

Consider:

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

read	Current value	Decision	write after step	Retained prefix
0	0	Accept first value	1	[0]
1	0	Duplicate; skip	1	[0]
2	1	New value; write at index 1	2	[0, 1]
3	1	Duplicate; skip	2	[0, 1]
4	1	Duplicate; skip	2	[0, 1]
5	2	New value; write at index 2	3	[0, 1, 2]
6	2	Duplicate; skip	3	[0, 1, 2]
7	3	New value; write at index 3	4	[0, 1, 2, 3]
8	3	Duplicate; skip	4	[0, 1, 2, 3]
9	4	New value; write at index 4	5	[0, 1, 2, 3, 4]

At read = 2, the value 1 is copied into index 1, behind the read pointer. The same compaction happens for 2, 3, and 4. The unread suffix remains safe because every write destination is at or before the current read position.

The final result is:

k = 5
nums[:k] = [0, 1, 2, 3, 4]

The suffix does not need to be cleaned up. The contract ends at the prefix boundary.

Implement the Python Solution

def remove_duplicates(nums: list[int]) -> int:
    write = 0

    for read in range(len(nums)):
        if write == 0 or nums[read] != nums[write - 1]:
            nums[write] = nums[read]
            write += 1

    return write

Each state variable has one job:

• read visits every original position.
• write is the next destination index and the current value of k.
• nums[write - 1] is the last distinct value retained.

The first-value condition is explicit. It avoids treating nums[-1] as a meaningful comparison while the retained prefix is empty.

Test the judged prefix, not the ignored suffix:

nums = [1, 1, 2]
k = remove_duplicates(nums)

assert k == 2
assert nums[:k] == [1, 2]

The function mutates nums and returns k; it does not return a new list. That rules out shortcuts such as nums = list(set(nums)): the shortcut builds a replacement structure instead of compacting the supplied array, and it does not express the required sorted-prefix contract.

Deleting elements while iterating is also a poor fit. Deletion shifts later indices and creates extra control-flow cases, but the array does not need to shrink. Read, decide, write, return the frontier.

Complexity and Edge Cases

Let n be the input length.

Time complexity

The loop reads each position once, and each distinct value causes at most one assignment. The time complexity is O(n).

Auxiliary space complexity

The algorithm uses a constant number of indices and temporary values. It reuses the input array and does not allocate a set or output list, so the auxiliary space complexity is O(1).

The problem's stated input domain is nonempty, but the implementation also handles an empty list safely:

[7]                 -> k = 1, prefix = [7]
[4, 4, 4]           -> k = 1, prefix = [4]
[1, 2, 3]           -> k = 3, prefix = [1, 2, 3]
[-3, -3, -1, 0, 0]  -> k = 3, prefix = [-3, -1, 0]
[]                  -> k = 0, prefix = []  (defensive case)

These cases test initialization, an all-duplicate run, an all-distinct input, negative and zero values, and the empty boundary. Equality controls the decision; no sentinel value receives special treatment.

Always interpret the result through the returned count:

k = remove_duplicates(nums)
meaningful_values = nums[:k]

Do not inspect, sort, or normalize the suffix. It is outside the contract.

The Transferable Two-Pointer Rule

When an input is sorted, equivalent values become adjacent. When the output is a shorter prefix of the same array, separate the work into two positions:

• one pointer inspects the input;
• one pointer compacts the verified output.

Before coding, name the invariant: the prefix before write contains exactly the distinct values processed so far. Then test the first value, a repeated run, and a sequence with no duplicates. Those cases force you to validate initialization, comparison, and pointer movement instead of merely recognizing a familiar template.

The broader pattern is stable in-place filtering: preserve selected values, keep their order, and let a write pointer mark the boundary of trustworthy output.

Read the signal. Advance the frontier. Return the boundary.