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
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 startsint 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
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 startsint 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.
Be the first to add a comment.