Remove Duplicates from Unsorted Array

16
0

You are given an unsorted array arr[] of integers that may contain duplicates. Your task is to remove the duplicate elements, keeping only the first occurrence of each element, and return the resulting array.

Example 1

Input: arr = [1, 2, 3, 1, 4, 2]

Output: [1, 2, 3, 4]

Explanation: Elements 1 and 2 appear more than once. Only the first occurrence of each element is retained, resulting in [1, 2, 3, 4].

Example 2

Input: arr = [1, 2, 3, 4]

Output: [1, 2, 3, 4]

Explanation: No duplicate elements are present, so the original array remains unchanged.

Brute Force Approach

A simple way to solve the problem is to build a new array and check every element before adding it. For each element, search through the elements already added to the new array.

If the element is already present, skip the element. Otherwise, add the element to the new array. Since elements are processed from left to right, the first occurrence is always retained, and the original order is preserved.

Algorithm

  • Create an empty array to store distinct elements.

  • Traverse the original array from left to right.

  • For each element, check whether the element already exists in the new array.

  • If the element is not present, add the element to the new array; otherwise, skip the element.

  • Return the new array after completing the traversal.

Dry Run

Remove Duplicates from Unsorted Array - Brute

Remove Duplicates from Unsorted Array - Brute

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Function to remove duplicates while preserving the original order
vector<int> removeDuplicates(vector<int>& arr) {
vector<int> result;
// Traverse each element of the input array
for (int i = 0; i < arr.size(); i++) {
bool found = false;
// Check whether the current element is already present in the result
for (int j = 0; j < result.size(); j++) {
if (arr[i] == result[j]) {
found = true;
break;
}
}
// Add the element only if it has not appeared before
if (!found) {
result.push_back(arr[i]);
}
}
return result;
}
};
// Driver code starts
int main() {
vector<int> arr = {1, 2, 3, 1, 4, 2};
Solution sol;
// Call the function to remove duplicates
vector<int> result = sol.removeDuplicates(arr);
// Print the array containing distinct elements
for (int x : result) {
cout << x << " ";
}
return 0;
}

Complexity Analysis

• Time Complexity: O(N²), where N represents the number of elements in the input array. For each element, the inner loop may traverse all previously added distinct elements to check for duplicates.

• Space Complexity: O(N), where N represents the number of elements in the input array. The result array stores up to N distinct elements.

Optimal Approach

The brute force approach searches through the new array for every element, which can take extra time as the array grows. A hash set provides a better way to check whether an element has already appeared.

A hash set stores only distinct elements and supports average (O(1)) lookup time. During a left-to-right traversal, each element is checked against the hash set. New elements are added to both the hash set and the result array, while repeated elements are skipped. The original order is preserved because elements are processed in the same order as the input array.

Algorithm

  • Create an empty hash set to keep track of visited elements and an empty array to store distinct elements.

  • Traverse the original array from left to right.

  • For each element, check whether the element already exists in the hash set.

  • If the element is not present, insert the element into the hash set and append the element to the result array. Skip repeated elements.

  • Return the result array after completing the traversal.

Dry Run

Remove Duplicates from Unsorted Array - Optimal

Remove Duplicates from Unsorted Array - Optimal

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Function to remove duplicates while preserving the original order
vector<int> removeDuplicates(vector<int>& arr) {
vector<int> result;
unordered_set<int> seen;
// Traverse each element of the input array
for (int i = 0; i < arr.size(); i++) {
// Check whether the current element has already appeared
if (seen.find(arr[i]) == seen.end()) {
// Mark the element as visited
seen.insert(arr[i]);
// Add the first occurrence to the result
result.push_back(arr[i]);
}
}
return result;
}
};
// Driver code starts
int main() {
vector<int> arr = {1, 2, 3, 1, 4, 2};
Solution sol;
// Call the function to remove duplicates
vector<int> result = sol.removeDuplicates(arr);
// Print the array containing distinct elements
for (int x : result) {
cout << x << " ";
}
return 0;
}

Complexity Analysis

• Time Complexity: O(N) on average, where N represents the number of elements in the input array. Each element is traversed once, and hash set insertion and lookup take O(1) average time.

• Space Complexity: O(N), where N represents the number of elements in the input array. The hash set and result array can each store up to N elements.

Interview follow-up Questions

Yes, both approaches work with positive numbers, negative numbers, and zero. The hash set can store integer values without requiring any special handling.

ArraysTCS NQT

Read Similar Blogs

Comments0