100% fast ✅ || C++ ✅ || Unordered_map || Well Explained ✅
Intuition\nWe need to find the difference between the number of distinct elements in the suffix of an element and the number of distinct elements in its prefix.
# Intuition\nWe need to find the difference between the number of distinct elements in the suffix of an element and the number of distinct elements in its prefix. We can achieve this by using two hash maps, one to keep track of the prefix and another to keep track of the suffix.\n\n- We can start by creating an empty hash map m1 to keep track of the prefix. We can iterate through the array and add each element to m1, incrementing its count.\n\n- We can then create another empty hash map m2 to keep track of the suffix. We can iterate through the array again, adding each element to m2, incrementing its count, and calculating the difference between the size of m2 and m1.\n\n- To get the difference in the number of distinct elements, we can subtract the size of m1 from the size of m2.\n\n- After calculating the difference, we can push it into a result vector v.\n\n- To update m1 for the next element, we can decrement the count of the current element in m1 and remove it from m1 if its count becomes zero.\n\n- Finally, we can return the result vector v.\n\nOverall, the approach involves using hash maps to keep track of the prefix and suffix and iterating through the array twice to calculate the difference between the number of distinct elements in the prefix and suffix of each element.\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nThe problem asks to find the distinct difference array of the given array, which can be solved using two pointers approach and hash maps.\n\n1. We first create two hash maps, m1, and m2. Here m1 will be used to keep track of the elements in the suffix and m2 will be used to keep track of the elements in the prefix.\n\n2. Then we loop through the array from left to right and for each element, we add it to the m2 map and remove it from the m1 map.\n\n3. After adding the current element to the m2 map, we calculate the difference in the size of m2 and m1 maps. This gives us the number of distinct elements in the prefix and the number of distinct elements in the suffix.\n\n4. We store this difference value in the resultant array, which gives us the distinct difference array of the given array.\n\n5. We continue this process for each element of the array and return the resultant array.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- **Time complexity**: As we are iterating through the array only once and performing constant time operations for each element.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- **Space complexity**: As we are using two hash maps to store the elements, the space required will be linear in terms of the size of the input array.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> distinctDifferenceArray(vector<int>& nums) {\n        unordered_map<int,int> m1;\n        for(int i=0;i<nums.size();i++)\n            m1[nums[i]]++;\n        unordered_map<int,int> m2;\n        vector<int> v;\n        for(int i=0;i<nums.size();i++){\n            m2[nums[i]]++;\n            m1[nums[i]]--;\n            if(m1[nums[i]]==0)\n                m1.erase(nums[i]);\n            int diff=m2.size()-m1.size();\n            v.push_back(diff);\n        }\n        return v;\n    }\n};\n```
['Ordered Map', 'C++']