Prefix + Suffix | Simple solution with 100% beaten
IntuitionThe problem requires calculating the distinct difference array for a given array of integers. The distinct difference at each index i is defined as the
# Intuition
The problem requires calculating the distinct difference array for a given array of integers. The distinct difference at each index `i` is defined as the number of distinct elements in the prefix (from the start to `i`) minus the number of distinct elements in the suffix (from `i+1` to the end). To solve this efficiently, we can use a bitset to track distinct elements in both the prefix and suffix.

# Approach
1. **Suffix Calculation**:
   - Traverse the array from the end to the start.
   - Use a bitset (`suffix`) to keep track of distinct elements encountered so far.
   - For each index `i`, store the count of distinct elements in the suffix (from `i+1` to the end) in the result array.

2. **Prefix Calculation**:
   - Traverse the array from the start to the end.
   - Use another bitset (`prefix`) to keep track of distinct elements encountered so far.
   - For each index `i`, calculate the distinct difference by subtracting the suffix count (precomputed earlier) from the prefix count.

3. **Result**:
   - The result array now contains the distinct difference for each index.

# Complexity
- **Time Complexity**: $$O(n)$$
  - We traverse the array twice: once for the suffix and once for the prefix. Each traversal takes linear time.
- **Space Complexity**: $$O(1)$$
  - The bitset uses constant space (51 bits), and the result array is required by the problem.

# Code
```cpp
#include <vector>
#include <bitset>

class Solution {
public:
    std::vector<int> distinctDifferenceArray(const std::vector<int>& nums) {
        int n = nums.size();
        std::vector<int> ans(n);
        std::bitset<51> prefix, suffix;

        // Precompute the suffix distinct counts
        for (int i = n - 1; i >= 0; --i) {
            ans[i] = suffix.count();
            suffix.set(nums[i]);
        }

        // Compute the prefix distinct counts and finalize the answer
        for (int i = 0; i < n; ++i) {
            prefix.set(nums[i]);
            ans[i] = prefix.count() - ans[i];
        }

        return ans;
    }
};
['C++']