Remove Duplicates from Sorted Array

Given a sorted integer slice, remove duplicates in-place so that each value appears once. Return the new length k such that the first k elements contain the unique values in sorted order.

Function signature

func RemoveDuplicatesSortedArray(nums []int) int

Inputs / outputs

• nums: sorted slice to modify in-place.
• Return: number of unique elements k; only nums[:k] is valid after the call.

Example

nums = [1,1,2,2,3]
After removal: nums = [1,2,3,_,_]
Return k = 3

Constraints

• 0 <= len(nums) <= 100_000
• -1_000_000_000 <= nums[i] <= 1_000_000_000

Core idea (near-solution)

Because the array is sorted, duplicates are adjacent. Use a read/write pair:

Invariant: nums[:write] contains the unique values seen so far, in order.

Algorithm (step-by-step)

1. If the slice is empty, return 0.
2. Set write = 1 (the first element is always unique).
3. For read from 1 to len(nums)-1:
   • If nums[read] != nums[read-1], copy nums[read] to nums[write] and increment write.
4. Return write.

Correctness sketch

• Invariant: nums[:write] contains the unique values seen so far, in order.
• Each step moves at least one pointer, shrinking the remaining search space.
• The invariant ensures elements outside the active window are already handled correctly.
• When pointers meet or cross, all candidates have been considered.

Trace (hand walkthrough)

Example input:
nums = [1,1,2,2,3]
After removal: nums = [1,2,3,_,_]
Return k = 3

Walk:
- start write=1 with nums[0]=1
- i=1 val=1 == nums[write-1]=1 -> skip
- i=2 val=2 != 1 -> nums[1]=2, write=2
- i=3 val=2 == nums[1]=2 -> skip
- i=4 val=3 != 2 -> nums[2]=3, write=3 => prefix [1,2,3]

Pitfalls to avoid

• Off-by-one when the slice has length 0 or 1.
• Comparing to nums[write-1] vs nums[read-1] without thinking through the invariant.
• Returning a new slice instead of the new length.

Complexity

• Time: O(n)
• Extra space: O(1)

Implementation notes (Go)

• nums remains sorted because you only copy forward in order.