Start learning free

LESSON 221 OF 410 · SORTING

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

Practice O(n log n) Read the full explanation

Given an array of integers, remove the duplicates in-place such that each unique element appears only once.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

The resulting array can be in any order.

Example:

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

Note:

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


Hints:

Let's sort the array in non-decreasing order. In this way all the equal elements will come one after another. Also, let's remove the O(1) extra space constraint for now to make the problem easier. Let's use an extra array uniqueValues and add the unique values from nums there.

Then, we can traverse the sorted array nums from left to right using an index i. We should add the element at index i into uniqueValues only if that value has not been seen before. How can we check this?

The element at index i has never been seen before if it is different from the element at index i - 1.

It's time to solve the question with the original constraint. We will still traverse sorted nums but each time we find a new unique element, we will overwrite an element of nums with this value, starting from the left:
  • The first unique value will be stored at index 0 of nums
  • The second unique value will be stored at index 1
  • ...
How can we achieve this?

We will use an index variable p, initially equal to 0, to keep track of the index where the last unique value was placed.

We will traverse nums and check if the element at index i is different from the element at index i - 1. If so, we will increment p and then copy the element at index i to index p. What should we return when we finish the traversal?

We should return the first p + 1 elements of nums.

STEP 1 OF 6
    Ctrl + Enter to check

    JAVASCRIPT · SORTING

    Remove Duplicates From Array in JavaScript, explained

    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:

    Keep going with JavaScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free