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

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 order of the elements in the resulting array does not matter.

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:

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

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 assuming the input 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 for each element, check if it has already been added to the unique values array. If not, we add it.

Naive Solution

The naive solution involves using a nested loop to check for duplicates, which results in 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 problem, we can discuss more optimized solutions in future lessons, such as using hash sets to achieve O(n) time complexity.

Algorithm

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

Initialize an empty array uniqueVals to store unique values.
Traverse the input array nums from left to right.
For each element nums[i], check if it is already in uniqueVals.
If nums[i] is not in uniqueVals, add it to uniqueVals.
Return the uniqueVals array.

Code Implementation


#include <iostream>
#include <vector>

std::vector<int> removeDuplicates(const std::vector<int>& nums) {
    std::vector<int> uniqueVals; // Array to store unique values
    for (int i = 0; i < nums.size(); ++i) {
        bool isUnique = true; // Flag to check if the current element is unique
        for (int j = 0; j < uniqueVals.size(); ++j) {
            if (nums[i] == uniqueVals[j]) {
                isUnique = false; // Element is not unique
                break;
            }
        }
        if (isUnique) {
            uniqueVals.push_back(nums[i]); // Add unique element to the array
        }
    }
    return uniqueVals; // Return the array of unique values
}

int main() {
    std::vector<int> nums = {2, 3, 1, 1, 4, 3, -2, 1};
    std::vector<int> result = removeDuplicates(nums);
    for (int val : result) {
        std::cout << val << " ";
    }
    return 0;
}

Complexity Analysis

The time complexity of the naive solution is O(n^2) due to the nested loops. The space complexity is O(n) because we use an extra array to store unique values.

Edge Cases

Potential edge cases include:

An empty array: The output should also be an empty array.
An array with all identical elements: The output should contain only one of those elements.
An array with negative numbers: The algorithm should handle negative numbers correctly.

Testing

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

Empty array: []
Array with all identical elements: [1, 1, 1, 1]
Array with negative numbers: [-1, -2, -2, -3]
Array with mixed positive and negative numbers: [1, -1, 2, -2, 1, -1]

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 and then think about optimizations.
Use extra data structures like arrays or hash sets to simplify the problem.
Practice solving similar problems to improve your problem-solving skills.

Conclusion

In this blog post, we discussed how to remove duplicates from an array using a naive O(n^2) time complexity algorithm in C++. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for improving your coding skills and preparing for technical interviews.

Additional Resources

For further reading and practice, consider the following resources: