Remove Duplicates from Sorted Array

Difficulty: Easy | Acceptance: 61.00% | Paid: No

Topics: Array, Two Pointers

• Examples
• Constraints
• Brute Force with Extra Space
• Two Pointer Approach (Optimal)
• Alternative Two Pointer with Explicit Comparison

Examples

Input

nums = [1,1,2]

Output

2, nums = [1,2,_]

Explanation

Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively. The values after the first k elements don’t matter.

Input

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

Output

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

Explanation

Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively. The values after the first k elements don’t matter.

Constraints

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

Brute Force with Extra Space

Intuition

The straightforward approach would be to use a set or another data structure to collect unique elements. However, this uses extra space.

Steps

• Create a new list or array to store unique elements.
• Iterate through the input array and add elements to the new structure if they are not already present.
• Copy the unique elements back to the original array.

def removeDuplicates(nums):
    # Use a set to store unique elements
    unique_nums = list(set(nums))
    unique_nums.sort()
    
    # Copy the unique elements back to the original array
    for i in range(len(unique_nums)):
        nums[i] = unique_nums[i]
    
    return len(unique_nums)

Complexity

• Time: O(n log n) due to sorting in most implementations, or O(n) if we use a hash-based approach but still need to sort the unique elements
• Space: O(n) for the extra data structures to store unique elements
• Notes: This approach does not satisfy the ‘in-place’ requirement of the problem. It also has suboptimal time complexity due to sorting.

Two Pointer Approach (Optimal)

Intuition

Since the array is already sorted, duplicates will be adjacent to each other. We can use two pointers to traverse the array and overwrite duplicates in place.

Steps

• Initialize two pointers: one (i) to track the position of the last unique element, and another (j) to scan through the array.
• Start both pointers at index 1 since the first element is always unique.
• If nums[j] is different from nums[i-1], it means we found a new unique element. Copy it to position i and increment i.
• Continue until j reaches the end of the array. Return i as the count of unique elements.

def removeDuplicates(nums):
    if not nums:
        return 0
    
    # i points to the position where the next unique element should be placed
    i = 1
    
    # j scans through the array starting from index 1
    for j in range(1, len(nums)):
        # If current element is different from the previous unique element
        if nums[j] != nums[i - 1]:
            nums[i] = nums[j]
            i += 1
    
    return i

Complexity

• Time: O(n) where n is the length of the array. We iterate through the array once.
• Space: O(1) as we only use a constant amount of extra space for the pointers.
• Notes: This is the optimal solution that satisfies the problem’s in-place requirement and achieves linear time complexity.

Alternative Two Pointer with Explicit Comparison

Intuition

We can also compare adjacent elements directly since the array is sorted. This is a slight variation of the main two-pointer approach.

Steps

• Initialize a pointer i at index 0 to track the position of unique elements.
• Use another pointer j starting at index 1 to scan the array.
• When we find nums[j] != nums[i], we’ve found a new unique element.
• Increment i and copy nums[j] to nums[i].
• Continue until j reaches the end and return i + 1 as the count.

def removeDuplicates(nums):
    if not nums:
        return 0
    
    i = 0  # Position of last unique element
    
    for j in range(1, len(nums)):
        # If current element is different from the last unique element
        if nums[j] != nums[i]:
            i += 1
            nums[i] = nums[j]
    
    return i + 1

Complexity

• Time: O(n) where n is the length of the array. We iterate through the array once.
• Space: O(1) as we only use a constant amount of extra space for the pointers.
• Notes: This approach is essentially equivalent to the main two-pointer solution but uses a slightly different pointer management strategy.