Find the Distinct Difference Array (Brute Force)
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem asks to find the difference between the count of distinct numbers in the ar
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem asks to find the difference between the count of distinct numbers in the array before and after a certain index. One way to solve this problem is to iterate through the array and for each index, count the number of distinct elements in the subarray before that index and the number of distinct elements in the subarray after that index. Then, calculate the difference and store it in the answer array.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe can use two sets, pre and suf, to keep track of the distinct elements in the subarray before and after the current index, respectively. We iterate through the array, and for each index i, we insert all elements from index 0 to i in the pre set and all elements from index i+1 to n-1 in the suf set. We then calculate the difference between the sizes of the two sets, which gives us the number of distinct elements before and after the current index. We store this difference in the answer array and clear the sets before moving on to the next index.set\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nTime complexity: O(n^2), where n is the size of the input array. This is because for each index, we insert all elements from index 0 to i in the pre set and all elements from index i+1 to n-1 in the suf set, which takes O(n) time. Since we do this for every index, the time complexity becomes O(n^2).\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n), where n is the size of the input array. This is because we are using two sets of size at most n to store the distinct elements before and after each index. The answer array also has size n.\n# Code\n```\nclass Solution {\npublic:\n    vector<int> distinctDifferenceArray(vector<int>& nums) {\n        set<int>pre;\n        vector<int>ans;\n        set<int>suf;\n        int n=nums.size();\n        for(int i=0;i<n;i++){\n            for(int j=0;j<=i;j++) pre.insert(nums[j]);\n            for(int k=i+1;k<n;k++) suf.insert(nums[k]);\n        int x=pre.size();\n            int y=suf.size();\n            ans.push_back(x-y);\n              pre.clear();\n            suf.clear();\n        }\n    return ans;\n    }\n};\n```
['Ordered Set', 'C++']