Remove Duplicates from Array II - O(n log n) Time Complexity in JavaScript

Input: [2, 3, 1, 1, 4, 3, -2, 1]
Output: [2, 3, 1, 4, -2]
			

Your algorithm should run in O(n log n) time and use O(1) extra space.

Understanding the Problem

The core challenge of this problem is to remove duplicates from an array in-place, meaning we cannot use additional space for another array. This is a common problem in data processing where we need to ensure data uniqueness without using extra memory.

Common applications include data cleaning, where duplicate entries need to be removed, and in algorithms where unique elements are required for further processing.

Potential pitfalls include misunderstanding the in-place requirement and using additional data structures, which would violate the constraints.

Approach

To solve this problem, we can follow these steps:

1. Sort the array. Sorting will bring all duplicates together, making it easier to remove them.
2. Use a pointer to track the position of the next unique element.
3. Traverse the sorted array, and for each unique element, place it at the position indicated by the pointer and increment the pointer.

Let's discuss a naive solution first:

Naive Solution: We could use an additional array to store unique elements, but this violates the O(1) extra space constraint.

Optimized Solution: By sorting the array first, we can then use a single pass to remove duplicates in-place.

Algorithm

Here is a step-by-step breakdown of the optimized algorithm:

1. Sort the array.
2. Initialize a pointer p to 0.
3. Traverse the array from the second element to the end.
4. For each element, if it is different from the previous element, place it at the position indicated by p and increment p.
5. Return the subarray from the start to the position indicated by p.

Code Implementation

/**
 * Remove duplicates from an array in-place.
 * @param {number[]} nums - The input array.
 * @return {number[]} The array with duplicates removed.
 */
function removeDuplicates(nums) {
    // Step 1: Sort the array
    nums.sort((a, b) => a - b);

    // Step 2: Initialize a pointer to track the position of the next unique element
    let p = 0;

    // Step 3: Traverse the array
    for (let i = 1; i < nums.length; i++) {
        // Step 4: If the current element is different from the previous one
        if (nums[i] !== nums[i - 1]) {
            // Step 5: Place it at the position indicated by p and increment p
            p++;
            nums[p] = nums[i];
        }
    }

    // Step 6: Return the subarray from the start to the position indicated by p
    return nums.slice(0, p + 1);
}

// Example usage:
const input = [2, 3, 1, 1, 4, 3, -2, 1];
const output = removeDuplicates(input);
console.log(output); // Output: [ -2, 1, 2, 3, 4 ]

Complexity Analysis

Time Complexity: The sorting step takes O(n log n) time, and the traversal step takes O(n) time. Therefore, the overall time complexity is O(n log n).

Space Complexity: The algorithm uses O(1) extra space as it modifies the array in-place.

Edge Cases

Consider the following edge cases:

• An empty array: The output should be an empty array.
• An array with all identical elements: The output should be an array with a single element.
• An array with no duplicates: The output should be the same as the input array.

Testing these edge cases ensures the robustness of the solution.

Testing

To test the solution comprehensively, consider the following test cases:

// Test case 1: Empty array
console.log(removeDuplicates([])); // Output: []

// Test case 2: Array with all identical elements
console.log(removeDuplicates([1, 1, 1, 1])); // Output: [1]

// Test case 3: Array with no duplicates
console.log(removeDuplicates([1, 2, 3, 4])); // Output: [1, 2, 3, 4]

// Test case 4: Array with some duplicates
console.log(removeDuplicates([2, 3, 1, 1, 4, 3, -2, 1])); // Output: [-2, 1, 2, 3, 4]

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

• Understand the constraints and requirements clearly.
• Think about sorting the array if it helps simplify the problem.
• Use pointers or indices to keep track of positions when modifying arrays in-place.
• Practice similar problems to improve problem-solving skills.

Conclusion

In this blog post, we discussed how to remove duplicates from an array in-place with O(n log n) time complexity and O(1) extra space. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for efficient data processing and algorithm design.

Keep practicing and exploring further to enhance your problem-solving skills!

Additional Resources

For further reading and practice problems, consider the following resources:

• LeetCode: Remove Duplicates from Sorted Array
• GeeksforGeeks: Remove Duplicates from Sorted Array
• Coding Ninjas: Remove Duplicates from Sorted Array