Start learning free

LESSON 221 OF 410 · SORTING

Remove Duplicates from Array II in O(n log n) Time Complexity using Python

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

    PYTHON · SORTING

    Remove Duplicates From Array in Python, explained

    Understanding the Problem

    The core challenge of this problem is to remove duplicates from an array in-place, meaning we cannot use extra space for another array. This is significant in scenarios where memory usage is critical. Common applications include data cleaning and preprocessing in data science.

    Potential pitfalls include misunderstanding the in-place requirement and using extra space inadvertently.

    Approach

    To solve this problem, we can follow these steps:

    1. Sort the array. This ensures that duplicate elements are adjacent.
    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.
    4. Return the subarray up to the pointer's position.

    Sorting the array takes O(n log n) time, and the traversal takes O(n) time, resulting in an overall time complexity of O(n log n).

    Algorithm

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

    1. Sort the array.
    2. Initialize a pointer p to 0.
    3. Traverse the array starting from the second element (index 1).
    4. If the current element is different from the previous element, increment the pointer and update the element at the pointer's position.
    5. Return the subarray from the start to the pointer's position.

    Code Implementation

    def remove_duplicates(nums):
    # Step 1: Sort the array
    nums.sort()
    
    # Step 2: Initialize the pointer
    p = 0
    
    # Step 3: Traverse the array
    for i in range(1, len(nums)):
        # Step 4: Check if the current element is different from the previous one
        if nums[i] != nums[i - 1]:
            p += 1
            nums[p] = nums[i]
    
    # Step 5: Return the subarray from the start to the pointer's position
    return nums[:p + 1]

# Example usage
input_array = [2, 3, 1, 1, 4, 3, -2, 1]
output_array = remove_duplicates(input_array)
print(output_array)  # Output: [2, 3, 1, 4, -2]

    Complexity Analysis

    The time complexity of this approach is O(n log n) due to the sorting step. The space complexity is O(1) as we are modifying the array in-place and not using any extra space.

    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.

    These cases can be tested to ensure the robustness of the solution.

    Testing

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

    def test_remove_duplicates():
    assert remove_duplicates([]) == []
    assert remove_duplicates([1, 1, 1, 1]) == [1]
    assert remove_duplicates([1, 2, 3, 4]) == [1, 2, 3, 4]
    assert remove_duplicates([2, 3, 1, 1, 4, 3, -2, 1]) == [-2, 1, 2, 3, 4]
    print("All test cases pass")

test_remove_duplicates()

    Thinking and Problem-Solving Tips

    When approaching such problems, consider the following tips:

    • Understand the constraints and requirements clearly.
    • Break down the problem into smaller steps.
    • Consider edge cases and test your solution against them.
    • 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 using Python. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for improving problem-solving skills and preparing for coding interviews.

    Additional Resources

    For further reading and practice, consider the following resources:

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