Remove Duplicates from Sorted Array

LeetCode 26: Remove Duplicates from Sorted Array Solution & Explanation

Problem Overview

TL;DR: Use a "slow" pointer to track the position of the last unique element and a "fast" pointer to scan the array, overwriting duplicates in-place.

The LeetCode 26 problem, Remove Duplicates from Sorted Array, asks us to process a sorted integer array and modify it directly so that every element appears only once. Because the array is sorted, duplicates are grouped together. We must place the unique elements at the beginning of the array and return the count of these unique elements. This is a classic interview question testing mastery of array manipulation and space efficiency.

Brute Force Approach for Remove Duplicates from Sorted Array

A naive approach to solving this problem in-place involves simulating the deletion process manually. When we iterate through the array and find a duplicate (where nums[i] == nums[i-1]), we can shift all subsequent elements one position to the left to overwrite the duplicate.

Pseudo-code:

function removeDuplicates(nums):
    i = 1
    current_length = nums.length
    while i < current_length:
        if nums[i] == nums[i-1]:
            # Shift all elements from i to end one step left
            for j from i to current_length - 2:
                nums[j] = nums[j+1]
            current_length = current_length - 1
        else:
            i = i + 1
    return current_length

Time Complexity: $O(N^2)$ Space Complexity: $O(1)$

Why this fails: While this solution respects the space constraint, it fails on time efficiency. For every duplicate found, we perform a shift operation that takes $O(N)$ time. In the worst-case scenario (an array with all unique elements or many duplicates), this results in quadratic time complexity. For an input size of $3 * 10^4$, an $O(N^2)$ operation performs roughly $900,000,000$ operations, which risks a Time Limit Exceeded (TLE) error or simply performs poorly compared to the optimal linear solution.

Algorithm Strategy: Two Pointer Patterns

1. Initialization: We know the first element (index 0) is always unique because there is no element before it. Therefore, we initialize our slow pointer (write index) at 1. We also start our fast pointer (read index) at 1.
2. Iteration: We iterate the fast pointer through the array until it reaches the end.
3. Comparison: At each step, we compare the element at nums[fast] with nums[fast - 1].
   • If nums[fast] is different from nums[fast - 1], it indicates a new unique element has been found.
   • If they are the same, it is a duplicate and should be ignored.
4. Modification: When a unique element is found:
   • Copy the value nums[fast] to nums[slow].
   • Increment slow to prepare for the next unique element.
5. Termination: Once fast has scanned the entire array, the value of slow represents the count of unique elements. The first slow elements of the array are now the unique set.

Execution Flow

Consider the input: nums = [0, 0, 1, 1, 1, 2, 2]

1. Start: slow = 1, fast = 1.
2. Step 1 (fast = 1): Compare nums[1] (0) with nums[0] (0). They are equal. Duplicate found. Do nothing. fast becomes 2.
3. Step 2 (fast = 2): Compare nums[2] (1) with nums[1] (0). They are different. New unique found.
   • Write nums[2] to nums[slow] (which is nums[1]). Array becomes [0, 1, 1, 1, 1, 2, 2].
   • Increment slow to 2.
   • fast becomes 3.
4. Step 3 (fast = 3): Compare nums[3] (1) with nums[2] (1). Equal. Ignore. fast becomes 4.
5. Step 4 (fast = 4): Compare nums[4] (1) with nums[3] (1). Equal. Ignore. fast becomes 5.
6. Step 5 (fast = 5): Compare nums[5] (2) with nums[4] (1). Different.
   • Write nums[5] to nums[slow] (which is nums[2]). Array becomes [0, 1, 2, 1, 1, 2, 2].
   • Increment slow to 3.
   • fast becomes 6.
7. Step 6 (fast = 6): Compare nums[6] (2) with nums[5] (2). Equal. Ignore. fast becomes 7.
8. End: fast is out of bounds. Return slow (which is 3). The first 3 elements are [0, 1, 2].

Proof of Correctness

The algorithm maintains the invariant that nums[0...slow-1] contains the unique elements encountered so far in sorted order.

• Base Case: At index 0, the element is trivially unique. slow starts at 1, preserving this.
• Inductive Step: When fast moves, we check if nums[fast] != nums[fast-1]. Since the array is sorted, a change in value implies a strictly greater value, which has not been written to the unique prefix yet. By copying nums[fast] to nums[slow], we extend the unique prefix.
• Termination: fast visits every element. Therefore, all unique transitions are captured. slow ends up at the count of unique elements.

Pattern Reuse Notes

The Two Pointers - In-place Array Modification pattern is a fundamental technique for array manipulation. Understanding the "read/write" pointer dynamic enables you to solve several related problems efficiently:

• LeetCode 27: Remove Element - Identical pattern, but the condition for writing is checking against a specific value rather than the previous element.
• LeetCode 75: Sort Colors - A more complex variation using three pointers to partition the array in-place.
• LeetCode 80: Remove Duplicates from Sorted Array II - An extension where at most two duplicates are allowed. The logic is nearly identical, checking nums[fast] against nums[slow-2].
• LeetCode 283: Move Zeroes - Uses the same read/write pointer logic to shift non-zero elements to the front.

Reference Implementation

C++ Solution for LeetCode 26

1class Solution {
2public:
3    int removeDuplicates(vector<int>& nums) {
4        // Edge case: constraints say length >= 1, so no need to check for empty.
5        
6        int slow = 1; // The write pointer
7        
8        // fast is the read pointer
9        for (int fast = 1; fast < nums.size(); fast++) {
10            // Compare current element with the previous one
11            if (nums[fast] != nums[fast - 1]) {
12                // Found a unique element, write it to the slow position
13                nums[slow] = nums[fast];
14                slow++;
15            }
16        }
17        
18        return slow; // slow represents the number of unique elements
19    }
20};

Java Solution for LeetCode 26

1class Solution {
2    public int removeDuplicates(int[] nums) {
3        // Constraints guarantee nums.length >= 1
4        
5        int slow = 1; // Pointer for the position of the next unique element
6        
7        for (int fast = 1; fast < nums.length; fast++) {
8            // If current element is different from the previous one, it is unique
9            if (nums[fast] != nums[fast - 1]) {
10                nums[slow] = nums[fast];
11                slow++;
12            }
13        }
14        
15        return slow;
16    }
17}

Python Solution for LeetCode 26

1class Solution:
2    def removeDuplicates(self, nums: List[int]) -> int:
3        # Constraints guarantee len(nums) >= 1
4        
5        slow = 1  # Write pointer
6        
7        # Fast pointer iterates through the list
8        for fast in range(1, len(nums)):
9            # Check if current element is different from the previous one
10            if nums[fast] != nums[fast - 1]:
11                nums[slow] = nums[fast]
12                slow += 1
13                
14        return slow