Remove Duplicates In Array

Given an array arr consisting of positive integer numbers, remove all duplicate numbers.

Example:

Input: arr[] = [2, 2, 3, 3, 7, 5] 
Output: [2, 3, 7, 5]
Explanation: After removing the duplicates 2 and 3 we get 2 3 7 5.

Input: arr[] = [2, 2, 5, 5, 7, 7] 
Output: [2, 5, 7]

Input: arr[] = [8, 7] 
Output: [8, 7]

Constraints:
1<= arr.size() <=10⁶
2<= arr[i] <=100

Approach 01:

class Solution {
public:
    vector<int> removeDuplicate(vector<int>& array) {
        unordered_map<int, bool> seenElements;
        vector<int> uniqueElements;

        for (int element : array) {
            if (seenElements.find(element) != seenElements.end()) {
                continue;
            } else {
                seenElements[element] = true;
                uniqueElements.push_back(element);
            }
        }

        return uniqueElements;
    }
};

class Solution:
    def removeDuplicates(self, array):
        seenElements = {}
        uniqueElements = []
        
        for element in array:
            if seenElements.get(element) is not None:
                continue
            else:
                seenElements[element] = True
                uniqueElements.append(element)
                
        return uniqueElements

Time Complexity

• Iterating through the array:

  The function iterates over each element in the input array once. For an array of size \(n\), this takes \(O(n)\).

• Checking for duplicates in the unordered map:

  For each element in the array, the algorithm checks if the element is already present in the unordered map. Inserting and searching in an unordered map has an average time complexity of \(O(1)\). Therefore, the check and insert operations for each element will also take \(O(1)\).

• Overall Time Complexity:

  Since both the iteration over the array and the insert/search operations in the unordered map are \(O(1)\) per element, the overall time complexity is \(O(n)\), where \(n\) is the number of elements in the input array.

Space Complexity

• Space used by the unordered map:

  The unordered map stores each unique element from the input array. In the worst case, when all elements are unique, the unordered map will store \(n\) elements, leading to a space complexity of \(O(n)\).

• Space used by the result vector:

  The output vector stores all unique elements from the input array. In the worst case, when all elements are unique, the output vector will also contain \(n\) elements. Therefore, this contributes \(O(n)\) space complexity.

• Overall Space Complexity:

  Since both the unordered map and the output vector take \(O(n)\) space, the overall space complexity is \(O(n)\), where \(n\) is the number of elements in the input array.