[C++] O(N) using Map, Set || Very Simple & Easy
Idea : \n1. To count distinct element from front, we are using a set data structure simply and inserting the elements into it during the traversal. In this case
**Idea :** \n1. To count distinct element from front, we are using a set data structure simply and inserting the elements into it during the traversal. In this case, st.size() is the required prefix value.\n\n2. To count distinct elements from back, we are using a map. In the map we have already stored the counts of the elements. We have taken a variable "cnt" which basically stores the count of distinct values in the array. \n\n3. During the traversal, we decrement the element\'s frequency in the map and whenever this frequency of any element = 0, we can infer that a distinct element which used to exist earlier has now been gone i.e. it does not exist in the right -> so we decrement cnt (cnt--)\n\n4. So during each iteration, we get this st.size() and cnt to calculate the required difference as (st.size()-cnt).\n\n```\n vector<int> distinctDifferenceArray(vector<int>& nums) {\n        vector<int>ans;\n        unordered_map<int,int>mp;\n        \n        int cnt = 0; // cnt distinct from back\n        for(auto i : nums){\n            mp[i]++;\n        }\n        \n        for(auto it : mp){\n            if(it.second>0){cnt++;}\n        }\n        \n        unordered_set<int>st;  // cnt distinct from start\n        \n        for(auto i : nums){\n            st.insert(i);\n            mp[i]--;\n            if(mp[i]==0){cnt--;}\n            \n            ans.push_back(st.size()-cnt);\n        }\n        \n        return ans;\n    }\n```\n\nTime : O(N)\nSpace : O(N)
['Array', 'Hash Table', 'C', 'Ordered Set', 'C++']