Remove Duplicates from Sorted Array — Fast and Slow Pointer Deduplication

Problem Statement#

Given an integer array nums sorted in non-decreasing order, remove the duplicates in place such that each unique element appears only once. Return the number of unique elements.

Constraints:

• 1 <= nums.length <= 3 * 10^4
• -100 <= nums[i] <= 100
• nums is sorted in non-decreasing order

Input:  nums = [1,1,2]
Output: 2, nums = [1,2,_]

Input:  nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]

Why This Problem Matters#

LeetCode 26 Remove Duplicates from Sorted Array is the deduplication variant of the fast and slow pointer pattern. Microsoft, Meta, and Amazon use it interchangeably with LC 27 Remove Element as a phone screen warm-up. The twist is that the duplicate detection requires comparing against the previous kept element, not against a fixed value.

Because the input is sorted, all duplicates of the same value are contiguous. That ordering is what makes the in-place O(n) and O(1) solution possible. The same problem on an unsorted array would require a hash set and O(n) extra space.

This problem prepares you for LC 80 Remove Duplicates II, which allows up to two copies of each value, and for LC 1089 Duplicate Zeros, which uses a similar two pointer rewrite from the end.

The Core Insight#

The write pointer k always points to the slot where the next unique element should go. The read pointer i scans the array starting at index 1. Whenever nums[i] differs from nums[k - 1], we have found a new unique value, so we write it at nums[k] and advance k.

The first element is always unique relative to nothing, so we initialize k = 1 and skip the first iteration. The sortedness of the input guarantees that nums[i] != nums[k - 1] is exactly the condition for a new unique value, because all copies of the previous value sit consecutively before i.

When the scan finishes, k equals the count of unique values and nums[0:k] contains them in sorted order.

Visual Dry Run#

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

Return 5.

Solution (Optimal)#

class Solution:
    def removeDuplicates(self, nums: list[int]) -> int:
        if not nums:
            return 0
        k = 1
        for i in range(1, len(nums)):
            if nums[i] != nums[k - 1]:
                nums[k] = nums[i]
                k += 1
        return k

var removeDuplicates = function(nums) {
    if (nums.length === 0) return 0;
    let k = 1;
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] !== nums[k - 1]) {
            nums[k] = nums[i];
            k++;
        }
    }
    return k;
};

Time: O(n) — single pass Space: O(1) — two indices

Common Mistakes#

• Comparing against nums[i - 1] instead of nums[k - 1], which fails when duplicates are skipped
• Initializing k = 0 and skipping the first element, then losing track of the unique count
• Using a set, which costs O(n) extra space and ignores the sortedness of the input
• Calling nums = list(set(nums)) and re-sorting, which violates the in-place constraint
• Forgetting the empty array edge case in languages where indexing fails

Interview Tips#

• Say explicitly that sortedness is what enables the O(1) space solution
• Compare against nums[k - 1], not against the previous read position
• Mention that LC 80 is a clean follow-up where you compare against nums[k - 2]
• Confirm that the grader only checks the first k slots of the array

Follow-up Questions#

• What if up to two duplicates are allowed? (Hint: LC 80, compare against nums[k - 2])
• What if the array is unsorted? (Hint: hash set, O(n) extra space)
• How would you remove all duplicates such that no duplicated values remain? (Hint: LC 26 variant, count and filter)
• How would you do this on a sorted singly linked list? (Hint: LC 83, single pointer with skip)
• What if you also need the count of removed elements? (Hint: subtract k from len(nums))

Key Takeaways#

• LeetCode 26 Remove Duplicates from Sorted Array uses the fast and slow pointer template
• Sortedness of the input is what allows the O(1) space in-place solution
• Compare against nums[k - 1], the last unique value written, not against nums[i - 1]
• O(n) time and O(1) space, no hash set required
• Pattern extends to LC 80 by comparing against nums[k - 2] for at most two duplicates
• Microsoft, Meta, and Amazon use this as a phone screen warm-up
• Slots beyond k contain stale values and the grader ignores them