Remove Duplicate from Sorted array

Problem Overview

The LeetCode problem "Remove Duplicates from Sorted Array" requires that we modify a sorted array in place to remove duplicates, such that each element appears only once and returns the new length of the array. Unlike other linked list problems, we must not allocate extra space for another array and instead do this with O(1) extra memory.

The problem link is Remove Duplicates from Sorted Array.

Understanding the Problem

Given a sorted array of integers, we need to remove the duplicates in such a way that each element appears only once in subsequent positions. This problem requires us to manage the array in place, making it a bit tricky as we must handle indices without additional buffer space. The output should be the length of the modified array without duplicates, and we need to ensure the first part of the array up to this length contains all unique elements, while the rest of the array could be left unchanged.

Example

• Input: nums = [0,0,1,1,1,2,2,3,3,4]
• Output: Length = 5, modified array = [0,1,2,3,4,,,,,_]

This indicates that the first five elements are the unique numbers, and _ denotes any leftover elements.

Key DSA Concepts and Theory

Arrays

• Immutability and Contract: In this problem, arrays are both input and modified output. Modifying an array in-place requires careful index management to ensure the results adhere to the constraints.
• Sorted Property: We leverage the sorted property by iterating through the array once, knowing that duplicates will always be contiguous.

In-Place Operations

• In-place Modification: We need to carry out operations on the original array without using additional data structures that grow with input size. This involves using pointers effectively.

Solution Approach

To solve the problem, we need to use a two-pointer technique. This helps efficiently traverse and modify the array in place.

C++ Solution

int removeDuplicates(vector<int>& nums) {
    if (nums.size() == 0) return 0;
    
    int uniqueIndex = 0; // This is our slow-runner index
    
    for (int i = 1; i < nums.size(); ++i) {
        if (nums[i] != nums[uniqueIndex]) {
            uniqueIndex++;
            nums[uniqueIndex] = nums[i];
        }
    }
    
    return uniqueIndex + 1;
}

Java Solution

public int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;
    
    int uniqueIndex = 0; // This is our slow-runner index
    
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] != nums[uniqueIndex]) {
            uniqueIndex++;
            nums[uniqueIndex] = nums[i];
        }
    }
    
    return uniqueIndex + 1;
}

Explanation

1. Initialization: Set uniqueIndex to 0 as the starting point for unique elements.

2. Iteration: Begin iterating from the second element. Use a loop to compare each element with the last known unique element.

3. Update Unique Position: If a new unique element is found (not equal to nums[uniqueIndex]), increment uniqueIndex and update the value at nums[uniqueIndex] to continue building the list of unique elements.

4. Return Length: The length of the array with only unique elements is uniqueIndex + 1.

Time and Space Complexity Analysis

• Time Complexity: O(n) as we traverse the array only once.
• Space Complexity: O(1) since we are not using any auxiliary data structure that scales with input size.

Common Mistakes to Avoid

• Out of Bounds Access: Ensure that you don't access nums[i] if i exceeds the array bounds.
• Handling Edge Cases: Check for empty arrays initially to handle minimum input sizes.

Similar Problems on LeetCode

• Remove Duplicates from Sorted List (LeetCode 83)
• Remove Element (LeetCode 27)

Additional Resources and References

• The Two-Pointer Technique - uses two pointers to process two sequences simultaneously.
• In-place Array Operations - modifying the original array without additional space.

By understanding this problem and solution, you can gain valuable insights into efficient iteration methods for similar problems involving arrays and in-place operations.