Algorithm

Instead of traversing the entire array again for every element, we can simply store the element appearing in a map for faster look up. This helps in improving the time complexity of our solution by making it faster to check whether a element is duplicate or not.

Initialize an hash map and iterate over the original array.
Initialize an answer string. For every element, check if it is present in the map or not.
If the element is present, skip that element. If it is not present, add it to our answer array and mark it as true in map.
Return the answer array once the original array is traversed completely.

Code

#include <bits/stdc++.h>
using namespace std;

// Solution class containing the optimized method
class Solution {
public:
    // Function to remove duplicates using map 
    vector<int> removeDuplicates(vector<int>& arr) {
        unordered_map<int, bool> seen;
        vector<int> result;

        // Traverse each element
        for (int val : arr) {
            // If not seen before, add to result and mark as seen
            if (!seen[val]) {
                result.push_back(val);
                seen[val] = true;
            }
        }

        return result;
    }
};

// Main class
int main() {
    vector<int> arr = {4, 5, 4, 2, 2, 3, 1};

    Solution sol;
    vector<int> result = sol.removeDuplicates(arr);

    cout << "Array after removing duplicates: ";
    for (int val : result) {
        cout <