Remove Duplicates Sorted Array LeetCode 26

LeetCode 26 — Remove Duplicates from Sorted Array — gives you a sorted integer array nums and asks you to remove duplicates in-place so that each unique element appears only once. You must return k, the count of unique elements. The first k positions of nums must contain the unique values in their original order; everything after index k-1 does not matter.

Because the array is sorted, all duplicates are adjacent — any repeated value appears in a contiguous block. This adjacency property is the key that makes the two-pointer approach work in O(1) space. If the array were unsorted, you would need a HashSet to track which values had been seen.

The problem is judged by a custom checker: it reads k from your return value and verifies that nums[0..k-1] contains the correct unique values in sorted order. The values at indices k and beyond are ignored. You do not need to actually remove elements from the array; you only need to write the unique values to the front.

The two-pointer strategy assigns distinct roles to each pointer. slow is the write head: it tracks the position of the last confirmed unique element written to the front of the array. fast is the read head: it scans forward through the entire array looking for values that differ from nums[slow]. When fast finds such a value, it has found the next unique element.

When nums[fast] != nums[slow], there are two actions: increment slow to claim the next write position, then copy nums[fast] into nums[slow]. After the copy, slow points to the newly written unique value. fast then advances to the next index regardless of whether a copy happened. This single-pass scan processes every element exactly once.

At the end of the loop, slow is a 0-indexed pointer to the last unique element. The total count of unique elements is therefore slow + 1. Returning slow instead of slow+1 is the most common off-by-one mistake in this problem — slow is an index, not a count.

The algorithm initializes slow = 0, treating nums[0] as the first unique element already in place. fast then starts from index 1 and scans to the end. For every fast position, compare nums[fast] to nums[slow]: if they differ, a new unique element has been found; if they are equal, the element is a duplicate and fast simply advances without writing.

The initialization of slow = 0 correctly handles arrays with a single element: the for loop never executes (fast starts at 1, which equals nums.length for a size-1 array), and the function returns slow+1 = 1, which is correct. Arrays with all identical elements return 1 because slow never advances past 0.

The time complexity is O(n) because fast visits each element exactly once. The space complexity is O(1) because no auxiliary data structures are used — only the two integer pointer variables slow and fast, which are constant space regardless of input size.

The sorted precondition is what makes O(1) space possible. In a sorted array, all copies of a given value appear together in a contiguous block. This means a duplicate is always immediately adjacent to its original — comparing nums[fast] to nums[slow] is sufficient to detect duplicates because any repeat of nums[slow] must appear between slow and the next new value.

If the array were unsorted — for example [1, 3, 1, 2, 2] — comparing fast to slow would not work because duplicates are not adjacent. You would need a HashSet to record which values had been seen before. The HashSet approach is O(n) space, which violates the in-place constraint. The sorted precondition eliminates the need for that extra memory entirely.

The comparison fast vs slow (rather than fast vs fast-1) is intentional. slow always points to the most recently written unique value. fast compares against slow, not the previous fast position, because what matters is whether the current element is a new unique value relative to what has been written so far — not whether it equals its immediate predecessor in the original array.

Consider nums = [0,0,1,1,1,2,2,3,3,4]. Initialize slow = 0 (nums[0] = 0 is the first unique element). fast begins at index 1. At index 1: nums[1] = 0 == nums[slow=0] = 0 — duplicate, skip. At index 2: nums[2] = 1 != nums[slow=0] = 0 — new unique value; slow becomes 1, nums[1] = 1.

Continuing: index 3 (1 == nums[1] = 1, skip), index 4 (1 == 1, skip). At index 5: nums[5] = 2 != nums[slow=1] = 1 — new unique; slow becomes 2, nums[2] = 2. At index 6 (2 == 2, skip). At index 7: nums[7] = 3 != nums[slow=2] = 2 — new unique; slow becomes 3, nums[3] = 3.

At index 8 (3 == 3, skip). At index 9: nums[9] = 4 != nums[slow=3] = 3 — new unique; slow becomes 4, nums[4] = 4. Loop ends. Return slow+1 = 5. The first 5 elements of nums are [0,1,2,3,4], which are the 5 unique values in sorted order.

Python: def removeDuplicates(nums): slow = 0; for fast in range(1, len(nums)): if nums[fast] != nums[slow]: slow += 1; nums[slow] = nums[fast]; return slow + 1. O(n) time O(1) space. The for loop iterates from 1 to len(nums)-1 inclusive. The conditional only executes the two-line body when a new unique value is found; otherwise fast simply advances to the next index automatically.

Java: public int removeDuplicates(int[] nums) { int slow = 0; for (int fast = 1; fast < nums.length; fast++) { if (nums[fast] != nums[slow]) { slow++; nums[slow] = nums[fast]; } } return slow + 1; }. The logic is identical to Python. Java's for loop initializes fast = 1 and increments automatically, mirroring Python's range(1, len(nums)) exactly. Both solutions pass all LeetCode test cases.

Both implementations share the same structure: one variable initialization, one for loop, one conditional with two statements, one return. There are no nested loops, no recursion, no auxiliary data structures. The in-place writes to nums overwrite duplicates with unique values without disturbing the relative order of unique elements since both slow and fast move strictly left to right.

Remove Element (LeetCode 27) is the closest relative: instead of deduplicating, remove all occurrences of a given value val. The same slow/fast pattern applies — slow is the write head, fast scans the array, and slow advances only when nums[fast] != val. Return slow as the count of remaining elements (not slow+1, because slow represents the next empty position rather than the last filled position).

Move Zeroes (LeetCode 283) uses the write-head pattern with a twist: move all zeros to the end while maintaining the relative order of non-zero elements. Slow writes non-zero elements forward; after the first pass, fill everything from slow to end with zeros. Remove Duplicates II (LeetCode 80) allows each unique element to appear at most twice, adding a count variable or comparing fast to slow-1 instead of slow.

The two-pointer dedup family is one of the most important patterns in array manipulation: Remove Duplicates (26), Remove Element (27), Move Zeroes (283), Remove Duplicates II (80), and Sort Colors (75 — Dutch National Flag, three pointers). All share the core insight that slow tracks the write boundary and fast explores ahead, enabling in-place transformations in a single O(n) pass.