Remove Duplicates from Array in O(n^2) Time Complexity using Python

Given an array of integers, return a new array containing only the unique values.

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:

For this lesson, your algorithm should run in O(n^2) time and use O(n) extra space.
(There are faster solutions which we will discuss in future lessons)

Problem Definition

The task is to remove duplicates from an array of integers and return a new array containing only the unique values. The resulting array can be in any order.

Input:

An array of integers, e.g., [2, 3, 1, 1, 4, 3, -2, 1]

Output:

A new array containing only the unique values, e.g., [2, 3, 1, 4, -2]

Constraints and Assumptions:

The algorithm should run in O(n^2) time complexity.
The algorithm should use O(n) extra space.

Example:

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

Understanding the Problem

The core challenge is to identify and remove duplicate values from the array while maintaining the order of first occurrences. This problem is significant in various applications such as data cleaning, where duplicate entries need to be removed.

Potential pitfalls include not handling negative numbers or assuming the array is sorted.

Approach

To solve this problem, we can use an extra array to store unique values. We will traverse the input array and add each element to the new array only if it has not been added before.

Naive Solution:

A naive solution would involve checking each element against all previously added elements, leading to an O(n^2) time complexity. This is not optimal but meets the problem's constraints.

Optimized Solution:

While the naive solution is acceptable for this lesson, a more optimized approach would involve using a set to track seen elements, reducing the time complexity to O(n). However, this is beyond the scope of this lesson.

Algorithm

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

Initialize an empty list uniqueVals to store unique values.
Iterate through each element in the input array.
For each element, check if it is already in uniqueVals.
If it is not, add it to uniqueVals.
Return uniqueVals as the result.

Code Implementation

def remove_duplicates(nums):
    # Initialize an empty list to store unique values
    unique_vals = []
    
    # Iterate through each element in the input array
    for num in nums:
        # Check if the element is already in unique_vals
        if num not in unique_vals:
            # If not, add it to unique_vals
            unique_vals.append(num)
    
    # Return the list of unique values
    return unique_vals

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

Complexity Analysis

The time complexity of this approach is O(n^2) because for each element, we are checking its presence in the unique_vals list, which takes O(n) time in the worst case. The space complexity is O(n) as we are using an extra list to store unique values.

Edge Cases

Potential edge cases include:

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 negative numbers: The algorithm should handle negative numbers correctly.

Examples:

Input: []
Output: []

Input: [1, 1, 1, 1]
Output: [1]

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

Testing

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

Simple cases with a few elements.
Cases with all unique elements.
Cases with all duplicate elements.
Cases with negative numbers.
Edge cases like an empty array.

Example Test Cases:

def test_remove_duplicates():
    assert remove_duplicates([2, 3, 1, 1, 4, 3, -2, 1]) == [2, 3, 1, 4, -2]
    assert remove_duplicates([]) == []
    assert remove_duplicates([1, 1, 1, 1]) == [1]
    assert remove_duplicates([-1, -1, -2, -2]) == [-1, -2]
    assert remove_duplicates([1, 2, 3, 4, 5]) == [1, 2, 3, 4, 5]

test_remove_duplicates()

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Understand the problem requirements and constraints thoroughly.
Start with a simple, naive solution to get a working implementation.
Think about potential optimizations and trade-offs.
Consider edge cases and test your solution comprehensively.

Conclusion

In this blog post, we discussed how to remove duplicates from an array in O(n^2) 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 developing strong problem-solving skills.

Additional Resources

For further reading and practice, consider the following resources: