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

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.

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 add each element to the new array only if it has not been seen before.

Naive Solution:

A naive solution would involve nested loops to check for duplicates, resulting in O(n^3) time complexity, which is not optimal.

Optimized Solution:

We can improve this by using an extra array to store unique values and checking for duplicates using a linear search, resulting in O(n^2) time complexity.

Algorithm

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

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

Code Implementation

import java.util.ArrayList;
import java.util.List;

public class RemoveDuplicates {
    public static int[] removeDuplicates(int[] nums) {
        // Initialize an empty list to store unique values
        List<Integer> uniqueVals = new ArrayList<>();
        
        // Traverse the input array
        for (int i = 0; i < nums.length; i++) {
            // Check if the current element is already in uniqueVals
            if (!uniqueVals.contains(nums[i])) {
                // If not, add it to uniqueVals
                uniqueVals.add(nums[i]);
            }
        }
        
        // Convert the list to an array and return
        int[] result = new int[uniqueVals.size()];
        for (int i = 0; i < uniqueVals.size(); i++) {
            result[i] = uniqueVals.get(i);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {2, 3, 1, 1, 4, 3, -2, 1};
        int[] uniqueNums = removeDuplicates(nums);
        for (int num : uniqueNums) {
            System.out.print(num + " ");
        }
    }
}

Complexity Analysis

The time complexity of this approach is O(n^2) because for each element in the input array, we perform a linear search in the uniqueVals array. The space complexity is O(n) because we use an extra array to store unique values.

Edge Cases

Potential edge cases include:

An empty input array, which should return an empty array.
An array with all identical elements, which should return an array with a single element.

Example:

Input: []
Output: []

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

Testing

To test the solution comprehensively, consider a variety of test cases:

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

Thinking and Problem-Solving Tips

When approaching such problems, it is essential to:

Understand the problem requirements and constraints.
Start with a simple solution and then optimize.
Consider edge cases and test thoroughly.

Conclusion

In this blog post, we discussed how to remove duplicates from an array in O(n^2) time complexity using Java. 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: