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

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

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:

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

Output:

Array of unique integers, 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. This problem is significant in various applications such as data cleaning, where duplicate entries need to be removed to ensure data integrity.

Potential pitfalls include not handling negative numbers or zero correctly, and misunderstanding the requirement to maintain the order of first occurrences.

Approach

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

Naive Solution:

The naive solution involves nested loops to check for duplicates, resulting in O(n^2) time complexity. This is not optimal but meets the problem constraints.

Optimized Solution:

We can use a Set to keep track of seen values, reducing the need for nested loops. However, this would improve the time complexity to O(n), which is beyond the scope of this lesson.

Algorithm

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

1. Initialize an empty array uniqueVals.
2. Iterate through each element in the input array.
3. For each element, check if it is already in uniqueVals.
4. If it is not, add it to uniqueVals.
5. Return uniqueVals as the result.

Code Implementation

// Function to remove duplicates from an array
function removeDuplicates(nums) {
    // Initialize an empty array to store unique values
    let uniqueVals = [];
    
    // Iterate through each element in the input array
    for (let i = 0; i < nums.length; i++) {
        // Check if the current element is already in uniqueVals
        if (!uniqueVals.includes(nums[i])) {
            // If not, add it to uniqueVals
            uniqueVals.push(nums[i]);
        }
    }
    
    // Return the array of unique values
    return uniqueVals;
}

// Example usage
const inputArray = [2, 3, 1, 1, 4, 3, -2, 1];
const result = removeDuplicates(inputArray);
console.log(result); // 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 if it exists in the uniqueVals array, which takes O(n) time. The space complexity is O(n) as we are using an extra array to store unique values.

Edge Cases

Potential edge cases include:

• Empty array: The function should return an empty array.
• Array with all duplicates: The function should return an array with a single element.
• Array with negative numbers and zero: The function should handle these correctly.

Examples:

Input: []
Output: []

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

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

Testing

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

• Simple cases with no duplicates.
• Cases with multiple duplicates.
• Edge cases as discussed above.

Using a testing framework like Jest can help automate and manage these tests.

Thinking and Problem-Solving Tips

When approaching such problems:

• Understand the problem requirements and constraints thoroughly.
• Start with a simple, naive solution and then look for optimizations.
• Consider edge cases and how your solution handles them.
• Practice similar problems to improve problem-solving skills.

Conclusion

In this lesson, we discussed how to remove duplicates from an array using a naive approach with O(n^2) time complexity. Understanding and solving such problems is crucial for developing strong problem-solving skills. Practice and exploration of optimized solutions are encouraged.

Additional Resources

For further reading and practice:

• MDN Web Docs - Array
• LeetCode - Remove Duplicates from Sorted Array
• GeeksforGeeks - Remove Duplicates from an Unsorted Array