✔💯 DAY 402 | BEGINNER FRIENDLY  | 100% 0ms | [PYTHON/JAVA/C++] | EXPLAINED | Approach 🆙🆙🆙
Please Upvote as it really motivates me \uD83C\uDD99\uD83C\uDD99\uD83C\uDD99\n\n\nJUST AN IMPLEMENTATION PRBOLEM. \nAlways try to explore more  \n\n# Intuition 
# Please Upvote as it really motivates me \uD83C\uDD99\uD83C\uDD99\uD83C\uDD99\n\n\nJUST AN IMPLEMENTATION PRBOLEM. \nAlways try to explore more  \n\n# Intuition &  Approach\n<!-- Describe your approach to solving the problem. -->\n\n##### \u2022\tInitialize an array answer of size n, where n is the length of the input array.\n##### \u2022\tInitialize two arrays prefix and suffix of size n.\n##### \u2022\tInitialize two hash sets prefixset and suffixSet.\n##### \u2022\tIterate over the input array nums from left to right, and for each element nums[i], do the following:\n##### \u2022 a. If  prefixset does not contain nums[i], add nums[i] to prefixset and set prefix[i] to the size of prefixset.\n##### \u2022 b. If prefixset contains nums[i], set prefix[i] to the value of prefix[i-1].\n##### \u2022\tIterate over the input arrayfrom right to left, and for each element, do the following:\n##### \u2022 a. If  suffixSet does not contain nums[i], add nums[i] to suffixSet and set suffix[i] to the size of suffixSet.\n##### \u2022 b. If suffixSet contains nums[i], set suffix[i] to the value of suffix[i+1].\n##### \u2022\tIterate over the input array nums from left to right, and for each element, set answer[i] to prefix[i]-surffix[i+1]\n##### \u2022\tSet answer[n-1] = prefix[n-1].\n##### \u2022\tReturn the answer array.\n\n\n\n# Code\n```java []\npublic int[] distinctDifferenceArray(int[] nums) {\n    int n = nums.length;\n    int[] answer = new int[n];\n    int[] prefix = new int[n];\n    int[] suffix = new int[n];\n    HashSet<Integer> prefixSet = new HashSet<>();\n    HashSet<Integer> suffixSet = new HashSet<>();\n\n    // Step 1: Iterate over the input array from left to right to fill the prefix array\n    for (int i = 0, j = 1; i < n; i++) {\n        if (!prefixSet.contains(nums[i])) {\n            prefixSet.add(nums[i]);\n            prefix[i] = j++;\n        } else if (i > 0) {\n            prefix[i] = prefix[i-1];\n        }\n    }\n\n    // Step 2: Iterate over the input array from right to left to fill the suffix array\n    for (int i = n-1, j = 1; i >= 0; i--) {\n        if (!suffixSet.contains(nums[i])) {\n            suffixSet.add(nums[i]);\n            suffix[i] = j++;\n        } else if (i > 0) {\n            suffix[i] = suffix[i+1];\n        }\n    }\n\n    // Step 3: Iterate over the input array to fill the answer array\n    for (int i = 0; i < n-1; i++) {\n        answer[i] = prefix[i] - suffix[i+1];\n    }\n    answer[n-1] = prefix[n-1];\n\n    return answer;\n}\n```\n```c++ []\nvector<int> distinctDifferenceArray(std::vector<int>& nums) {\n    int n = nums.size();\n    std::vector<int> answer(n);\n    std::vector<int> prefix(n);\n    std::vector<int> suffix(n);\n    std::unordered_set<int> prefixSet;\n    std::unordered_set<int> suffixSet;\n    for (int i = 0, j = 1; i < n; i++) {\n        if (prefixSet.find(nums[i]) == prefixSet.end()) {\n            prefixSet.insert(nums[i]);\n            prefix[i] = j++;\n        } else if (i > 0) {\n            prefix[i] = prefix[i-1];\n        }\n    }\n    for (int i = n-1, j = 1; i >= 0; i--) {\n        if (suffixSet.find(nums[i]) == suffixSet.end()) {\n            suffixSet.insert(nums[i]);\n            suffix[i] = j++;\n        } else if (i < n-1) {\n            suffix[i] = suffix[i+1];\n        }\n    }\n    for (int i = 0; i < n-1; i++) {\n        answer[i] = prefix[i] - suffix[i+1];\n    }\n    answer[n-1] = prefix[n-1];\n    return answer;\n}\n```\n```python []\ndef distinctDifferenceArray(nums: List[int]) -> List[int]:\n    n = len(nums)\n    answer = [0] * n\n    prefix = [0] * n\n    suffix = [0] * n\n    prefixSet = set()\n    suffixSet = set()\n    for i in range(n):\n        if nums[i] not in prefixSet:\n            prefixSet.add(nums[i])\n            prefix[i] = len(prefixSet)\n        elif i > 0:\n            prefix[i] = prefix[i-1]\n    for i in range(n-1, -1, -1):\n        if nums[i] not in suffixSet:\n            suffixSet.add(nums[i])\n            suffix[i] = len(suffixSet)\n        elif i < n-1:\n            suffix[i] = suffix[i+1]\n    for i in range(n-1):\n        answer[i] = prefix[i] - suffix[i+1]\n    answer[n-1] = prefix[n-1]\n    return answer\n```\n\n\n# Complexity\n- Time complexity:o(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:o(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# using premitives faster runtime 4ms [objects are Costlier  ]\n![image.png](https://assets.leetcode.com/users/images/6640aa48-415a-4c65-b841-0450f5d3a5f1_1683443184.084796.png)\n\n```java []\npublic int[] distinctDifferenceArray(int[] nums) {\n    int n = nums.length;\n    int[] answer = new int[n];\n    int[] prefix = new int[n];\n    int[] suffix = new int[n];\n    boolean[] prefixSeen = new boolean[51];\n    boolean[] suffixSeen = new boolean[51];\n\n    // Step 1: Iterate over the input array from left to right to fill the prefix array\n    for (int i = 0, j = 1; i < n; i++) {\n        if (!prefixSeen[nums[i]]) {\n            prefixSeen[nums[i]] = true;\n            prefix[i] = j++;\n        } else if (i > 0) {\n            prefix[i] = prefix[i-1];\n        }\n    }\n\n    // Step 2: Iterate over the input array from right to left to fill the suffix array\n    for (int i = n-1, j = 1; i >= 0; i--) {\n        if (!suffixSeen[nums[i]]) {\n            suffixSeen[nums[i]] = true;\n            suffix[i] = j++;\n        } else if (i < n-1) {\n            suffix[i] = suffix[i+1];\n        }\n    }\n\n    // Step 3: Iterate over the input array to fill the answer array\n    for (int i = 0; i < n-1; i++) {\n        answer[i] = prefix[i] - suffix[i+1];\n    }\n    answer[n-1] = prefix[n-1];\n\n    return answer;\n}\n````\n\n\n![BREUSELEE.webp](https://assets.leetcode.com/users/images/062630f0-ef80-4e74-abdb-302827b99235_1680054012.5054147.webp)\n\n\n# Please Upvote\uD83D\uDC4D\uD83D\uDC4D\nThanks for visiting my solution.\uD83D\uDE0A Keep Learning\nPlease give my solution an upvote! \uD83D\uDC4D \uD83C\uDD99\uD83C\uDD99\uD83C\uDD99\nIt\'s a simple way to show your appreciation and\nkeep me motivated. Thank you! \uD83D\uDE0A
['Suffix Array', 'Python', 'C++', 'Java', 'Python3']