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.

Core Insight for Remove Duplicates from Sorted Array

The key intuition for LeetCode 26 Solution lies in the fact that the array is sorted. This guarantees that all duplicate values are adjacent to each other. We do not need a hash set to track seen elements; we only need to compare the current element with the previous one.

The optimal strategy decouples the "reading" of data from the "writing" of data.

1. Read Pointer (fast): Scans the array from left to right.
2. Write Pointer (slow): Indicates the position where the next unique element should be placed.

Invariant: At any point in the execution, the subarray nums[0...slow-1] contains exactly the unique elements found so far, in sorted order. The fast pointer searches for a value strictly greater than the last unique value found. When fast finds a new unique number, we copy it to the slow position and advance slow.

Visual Description: Imagine the array is divided into two regions. The left region (indices 0 to slow-1) is the "processed/unique" zone. The right region is the "unknown/unprocessed" zone. The fast pointer expands the known territory. Since fast is always equal to or ahead of slow, we can safely overwrite nums[slow] because its original value has already been processed or is a duplicate we no longer need.

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.

Reference Implementation

C++ Solution for LeetCode 26

cpp
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        // Edge case: constraints say length >= 1, so no need to check for empty.
        
        int slow = 1; // The write pointer
        
        // fast is the read pointer
        for (int fast = 1; fast < nums.size(); fast++) {
            // Compare current element with the previous one
            if (nums[fast] != nums[fast - 1]) {
                // Found a unique element, write it to the slow position
                nums[slow] = nums[fast];
                slow++;
            }
        }
        
        return slow; // slow represents the number of unique elements
    }
};

Java Solution for LeetCode 26

java
class Solution {
    public int removeDuplicates(int[] nums) {
        // Constraints guarantee nums.length >= 1
        
        int slow = 1; // Pointer for the position of the next unique element
        
        for (int fast = 1; fast < nums.length; fast++) {
            // If current element is different from the previous one, it is unique
            if (nums[fast] != nums[fast - 1]) {
                nums[slow] = nums[fast];
                slow++;
            }
        }
        
        return slow;
    }
}

Python Solution for LeetCode 26

python
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        # Constraints guarantee len(nums) >= 1
        
        slow = 1  # Write pointer
        
        # Fast pointer iterates through the list
        for fast in range(1, len(nums)):
            # Check if current element is different from the previous one
            if nums[fast] != nums[fast - 1]:
                nums[slow] = nums[fast]
                slow += 1
                
        return slow

Q: Can I use a Set to solve this? Mistake: Using a Hash Set to filter duplicates. Consequence: While this produces the correct logical result, it violates the Space Complexity constraint. The problem requires $O(1)$ extra space (in-place modification), whereas a Set uses $O(N)$ space.

Q: Why is my output shorter than expected? Mistake: Starting the iteration or the slow pointer at 0 and overwriting the first element incorrectly. Explanation: The first element is always unique. The logic should start comparing from the second element (index 1). If you start at 0, you might miss counting the first number or access nums[-1].