LeetCode 26: Remove Duplicates from Sorted Array - All Approaches Explained

Problem Statement

The Remove Duplicates from Sorted Array problem, LeetCode 26, is an easy-difficulty challenge involving a sorted array. You’re given an integer array nums sorted in non-decreasing order, and your task is to remove duplicates in-place such that each unique element appears only once. The relative order of elements should be preserved, and you must return the number of unique elements (k). The first k elements of the array should contain the final result, and the remaining elements beyond k are irrelevant.

Constraints

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

Example

Copy codeInput: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation:
- Remove duplicates: [1,1,2] → [1,2].
- Return k = 2, first 2 elements are [1,2], rest don’t matter.

Copy codeInput: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation:
- Remove duplicates: [0,1,2,3,4].
- Return k = 5.

Understanding the Problem

We need to remove duplicates from a sorted array in-place and return the length of the unique elements. Key observations:

• Since the array is sorted, duplicates are adjacent.
• We only need to keep the first occurrence of each number.
• The problem requires an in-place solution, modifying nums directly.

Let’s explore two approaches:

1. Two-Pointer (Best Approach) : Use two pointers for efficiency.
2. Brute Force : Use extra space and copy uniques.

Approach 1: Two-Pointer (Best Approach)

Intuition

Use two pointers: one to track the position for the next unique element (k) and another to scan the array (i). Since the array is sorted, compare adjacent elements to identify duplicates. This is the best approach due to its optimal time and space complexity.

How It Works

• Initialize k = 1 (position for next unique element, starting after first element).
• Iterate i from 1 to end:
  • If nums[i] != nums[i-1], it’s a new unique element.
  • Place it at nums[k] and increment k.
• Return k as the count of unique elements.

Step-by-Step Example

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

• Start: k = 1, nums = [0,0,1,1,1,2,2,3,3,4].
• i = 1: 0 == 0, skip.
• i = 2: 1 != 0, nums[1] = 1, k = 2, nums = [0,1,1,1,1,2,2,3,3,4].
• i = 3: 1 == 1, skip.
• i = 4: 1 == 1, skip.
• i = 5: 2 != 1, nums[2] = 2, k = 3, nums = [0,1,2,1,1,2,2,3,3,4].
• i = 6: 2 == 2, skip.
• i = 7: 3 != 2, nums[3] = 3, k = 4, nums = [0,1,2,3,1,2,2,3,3,4].
• i = 8: 3 == 3, skip.
• i = 9: 4 != 3, nums[4] = 4, k = 5, nums = [0,1,2,3,4,2,2,3,3,4].
• Result: k = 5, nums = [0,1,2,3,4, , , , ,_].

Python Code (Best Approach)

Copy codedef removeDuplicates(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return 1
    
    k = 1  # Position for next unique element
    for i in range(1, len(nums)):
        if nums[i] != nums[i-1]:
            nums[k] = nums[i]
            k += 1
    
    return k

# Test cases
nums1 = [1,1,2]
print(removeDuplicates(nums1), nums1[:removeDuplicates(nums1)])  # 2, [1,2]
nums2 = [0,0,1,1,1,2,2,3,3,4]
print(removeDuplicates(nums2), nums2[:removeDuplicates(nums2)])  # 5, [0,1,2,3,4]

Detailed Walkthrough

• Edge Cases : Empty or single-element arrays.
• Two Pointers : k tracks unique position, i scans for new elements.
• In-Place : Overwrite duplicates with unique values.

Complexity

• Time Complexity : O(n), where n is the length of nums. Single pass through the array.
• Space Complexity : O(1), in-place modification.

Why It’s the Best

• Optimal time and space complexity.
• Simple and leverages sorted property.
• Preferred in interviews for in-place efficiency.

Approach 2: Brute Force

Intuition

Use extra space to collect unique elements, then copy them back to the original array. This isn’t ideal due to extra space usage but helps understand the problem.

How It Works

• Use a list or set to store unique elements while preserving order.
• Iterate through nums, adding only new elements.
• Copy back to nums and return the count.

Step-by-Step Example

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

• Collect uniques: [0,1,2,3,4].
• Copy back: nums = [0,1,2,3,4, , , , ,_].
• Return 5.

Python Code

Copy codedef removeDuplicates_brute(nums):
    if not nums:
        return 0
    
    # Collect unique elements
    uniques = []
    for num in nums:
        if not uniques or uniques[-1] != num:
            uniques.append(num)
    
    # Copy back to nums
    for i in range(len(uniques)):
        nums[i] = uniques[i]
    
    return len(uniques)

# Test cases
nums1 = [1,1,2]
print(removeDuplicates_brute(nums1), nums1[:removeDuplicates_brute(nums1)])  # 2, [1,2]
nums2 = [0,0,1,1,1,2,2,3,3,4]
print(removeDuplicates_brute(nums2), nums2[:removeDuplicates_brute(nums2)])  # 5, [0,1,2,3,4]

Detailed Walkthrough

• Collection : Build list of uniques using last-element comparison.
• Copy : Overwrite nums with unique elements.
• Return : Length of uniques.

Complexity

• Time Complexity : O(n), single pass to collect uniques plus copy.
• Space Complexity : O(n), extra space for uniques list.

Pros and Cons

• Pros : Easy to understand.
• Cons : Uses extra space, not truly in-place.

Comparison of Approaches

Edge Cases to Consider

1. Empty array : [] → 0.
2. Single element : [1] → 1.
3. All duplicates : [1,1,1] → 1, [1, , ].
4. No duplicates : [1,2,3] → 3, [1,2,3].

Final Thoughts

• Brute Force : Useful for learning but inefficient due to extra space.
• Two-Pointer : The best approach —optimal, in-place, and elegant. Master the two-pointer solution for its efficiency and applicability to sorted array problems in interviews. Try extending this to remove duplicates allowing up to m occurrences as a follow-up!