[C++, Java, Python] Simple HashMap | Store Frequency | Time: O(n)
Intuition\nSince we want number of distinct elements in a window, we can use hash map to store the frequency of each number in current window.\nFor an index i,\
# Intuition\nSince we want number of distinct elements in a window, we can use hash map to store the frequency of each number in current window.\nFor an index `i`,\n- `prefix` maintains frequency table of `nums[0...i]`\n- `suffix` maintains frequency table of `nums[i + 1...n - 1]`\n\n# Approach\n1. Initially, `prefix` is empty, and `suffix` contains frequency of complete array. \n2. Now, for each index `i`, remove `nums[i]` from `suffix` and add to `prefix`. Calculate `size(prefix) - size(suffix)`.\n3. While removing an element from `suffix`, frequency might become 0. To make sure this `{key, value} = {x, 0}` pair is not counted, remove it from the hashmap.\n\n# Code\n\n```C++ []\nclass Solution {\npublic:\n    vector<int> distinctDifferenceArray(vector<int>& nums) {\n        unordered_map<int, int> prefix, suffix;\n        vector<int> result;\n        for (int& x: nums) {\n            suffix[x]++;\n        }\n        for (int& x: nums) {\n            prefix[x]++;\n            if (--suffix[x] == 0) {\n                suffix.erase(x);\n            }\n            result.push_back(prefix.size() - suffix.size());\n        }\n        return result;\n    }\n};\n```\n```Java []\nclass Solution {\n    public int[] distinctDifferenceArray(int[] nums) {\n        HashMap<Integer, Integer> prefix = new HashMap<>();\n        HashMap<Integer, Integer> suffix = new HashMap<>();\n        int[] result = new int[nums.length];\n        for (int x: nums) {\n            suffix.put(x, suffix.getOrDefault(x, 0) + 1);\n        }\n        for (int i = 0; i < nums.length; i++) {\n            Integer x = nums[i];\n            prefix.put(x, prefix.getOrDefault(x, 0) + 1);\n            suffix.put(x, suffix.get(x) - 1);\n            if (suffix.get(x) == 0) {\n                suffix.remove(x);\n            }\n            result[i] = prefix.size() - suffix.size();\n        }\n        return result;\n    }\n}\n```\n```Python []\nclass Solution:\n    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:\n        # One liner\n        # return [len(Counter(nums[:i + 1])) - len(Counter(nums[i + 1:])) for i in range(len(nums))]\n        prefix = defaultdict(int)\n        suffix = Counter(nums)\n        result = []\n        for x in nums:\n            prefix[x] += 1\n            suffix[x] -= 1\n            if suffix[x] == 0:\n                del suffix[x]\n            result.append(len(prefix) - len(suffix))\n        return result\n```\n\n# Complexity\n- Time complexity: $$\\Theta(n)$$\n- Space complexity: $$\\Theta(n)$$
['Hash Table', 'C++', 'Java', 'Python3']