For index i = 4, there are 3 distinct elements in the prefix and no elements in the suffix. Thus, diff[4] = 3 - 0 = 3.

Constraints

1 <= n == nums.length <= 50
1 <= nums[i] <= 50

Solution

Method 1 – Prefix and Suffix Set Counting

Intuition

For each index, count the number of distinct elements in the prefix and the suffix. Use sets to efficiently track unique elements as you sweep from left and right.

Approach

Initialize an array to store prefix distinct counts and another for suffix distinct counts.
Sweep from left to right, maintaining a set of seen elements, and fill prefix counts.
Sweep from right to left, maintaining a set of seen elements, and fill suffix counts.
For each index i, diff[i] = prefix[i] - suffix[i].
Return the diff array.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    vector<int> distinctDifferenceArray(vector<int>& nums) {\n        int n = nums.size();\n        vector<int> pre(n), suf(n), ans(n);\n        unordered_set<int> s;\n        for (int i = 0; i < n; ++i) {\n            s.insert(nums[i]);\n            pre[i] = s.size();\n        }\n        s.clear();\n        for (int i = n-1; i >= 0; --

Related Tags