# Find the Distinct Difference Array
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-the-distinct-difference-array)
Canonical: https://scaleengineer.com/dsa/problems/find-the-distinct-difference-array
**Data structures:** Array, Hash Table
---
## Problem
You are given a **0-indexed** array `nums` of length `n`.

The **distinct difference** array of `nums` is an array `diff` of length `n` such that `diff[i]` is equal to the number of distinct elements in the suffix `nums[i + 1, ..., n - 1]` **subtracted from** the number of distinct elements in the prefix `nums[0, ..., i]`.

Return _the **distinct difference** array of_ `nums`.

Note that `nums[i, ..., j]` denotes the subarray of `nums` starting at index `i` and ending at index `j` inclusive. Particularly, if `i > j` then `nums[i, ..., j]` denotes an empty subarray.

**Example 1:**

**Input:** nums = [1,2,3,4,5]
**Output:** [-3,-1,1,3,5]
**Explanation:** For index i = 0, there is 1 element in the prefix and 4 distinct elements in the suffix. Thus, diff[0] = 1 - 4 = -3.
For index i = 1, there are 2 distinct elements in the prefix and 3 distinct elements in the suffix. Thus, diff[1] = 2 - 3 = -1.
For index i = 2, there are 3 distinct elements in the prefix and 2 distinct elements in the suffix. Thus, diff[2] = 3 - 2 = 1.
For index i = 3, there are 4 distinct elements in the prefix and 1 distinct element in the suffix. Thus, diff[3] = 4 - 1 = 3.
For index i = 4, there are 5 distinct elements in the prefix and no elements in the suffix. Thus, diff[4] = 5 - 0 = 5.

**Example 2:**

**Input:** nums = [3,2,3,4,2]
**Output:** [-2,-1,0,2,3]
**Explanation:** For index i = 0, there is 1 element in the prefix and 3 distinct elements in the suffix. Thus, diff[0] = 1 - 3 = -2.
For index i = 1, there are 2 distinct elements in the prefix and 3 distinct elements in the suffix. Thus, diff[1] = 2 - 3 = -1.
For index i = 2, there are 2 distinct elements in the prefix and 2 distinct elements in the suffix. Thus, diff[2] = 2 - 2 = 0.
For index i = 3, there are 3 distinct elements in the prefix and 1 distinct element in the suffix. Thus, diff[3] = 3 - 1 = 2.
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`

# Approaches
## Brute Force with Nested Loops
This approach directly translates the problem definition into code. For each index `i`, it iterates through the prefix `nums[0...i]` and the suffix `nums[i+1...n-1]` to count the distinct elements in each part using `HashSet`s. The difference between these two counts gives the result for `diff[i]`.
**Time:** O(n^2). The outer loop runs `n` times. For each `i`, the inner loops for the prefix and suffix together iterate through `(i+1) + (n-1-i) = n` elements. Thus, the total time complexity is `n * n = O(n^2)`. · **Space:** O(n). In each iteration of the outer loop, we create two `HashSet`s. The maximum combined size of these sets can be up to `n`. The result array `diff` also requires `O(n)` space.
**Pros:** Simple to understand and implement.; Directly follows the problem statement, making the logic easy to verify.
**Cons:** Inefficient due to repeated calculations for prefixes and suffixes.; Its `O(n^2)` time complexity makes it unsuitable for large input sizes, although it passes for the given constraints.
### Explanation
The brute-force method is the most straightforward way to solve the problem. We iterate through each index `i` of the input array `nums`. For each `i`, we need to find the number of distinct elements in the prefix subarray `nums[0...i]` and the suffix subarray `nums[i+1...n-1]`. We can use a `HashSet` data structure to efficiently count distinct elements. We create one set for the prefix and another for the suffix. We populate them by iterating through the respective subarray parts and then find the difference of their sizes. This process is repeated for all indices from `0` to `n-1`.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] distinctDifferenceArray(int[] nums) {
        int n = nums.length;
        int[] diff = new int[n];

        for (int i = 0; i < n; i++) {
            // Calculate distinct elements in the prefix nums[0...i]
            Set<Integer> prefixDistinct = new HashSet<>();
            for (int j = 0; j <= i; j++) {
                prefixDistinct.add(nums[j]);
            }

            // Calculate distinct elements in the suffix nums[i+1...n-1]
            Set<Integer> suffixDistinct = new HashSet<>();
            for (int j = i + 1; j < n; j++) {
                suffixDistinct.add(nums[j]);
            }

            diff[i] = prefixDistinct.size() - suffixDistinct.size();
        }
        return diff;
    }
}
```
### Algorithm
- Initialize an integer array `diff` of size `n`.
- For `i` from `0` to `n-1`:
  - Create a `HashSet<Integer>` `prefixSet`.
  - For `j` from `0` to `i`:
    - Add `nums[j]` to `prefixSet`.
  - Create a `HashSet<Integer>` `suffixSet`.
  - For `k` from `i+1` to `n-1`:
    - Add `nums[k]` to `suffixSet`.
  - `diff[i] = prefixSet.size() - suffixSet.size()`.
- Return `diff`.

## Two-Pass Approach with Hash Sets
This approach improves upon the brute-force method by avoiding redundant calculations. It uses two passes. The first pass pre-computes the number of distinct elements for all possible suffixes and stores them. The second pass then calculates the prefix distinct counts on the fly and uses the pre-computed suffix counts to find the final difference array.
**Time:** O(n). The first pass to compute suffix counts takes `O(n)`. The second pass to compute the final `diff` array also takes `O(n)`. The total time is `O(n) + O(n) = O(n)`. · **Space:** O(n). We use an `O(n)` array `suffixDistinctCount`, two `HashSet`s which can grow up to size `n` in the worst case, and the `O(n)` result array `diff`.
**Pros:** Much more efficient than the brute-force approach with `O(n)` time complexity.; Conceptually clear with a good separation of concerns (calculating suffix counts first, then calculating the final result).
**Cons:** Requires extra space for the `suffixDistinctCount` array.; Requires two separate passes over the data, which might be slightly less cache-friendly than a single-pass solution.
### Explanation
The core idea is to optimize the repeated calculation of distinct elements in the suffix. We can do this by pre-calculating these values.

**First Pass (Suffix Calculation):** We create an array, say `suffixDistinctCount`, of size `n+1`. We iterate backward from the end of the `nums` array. Using a `HashSet`, we count the distinct elements seen so far and store the count at each index `i` in `suffixDistinctCount[i]`. `suffixDistinctCount[i]` will thus hold the number of distinct elements in `nums[i...n-1]`. `suffixDistinctCount[n]` will be 0 for the empty suffix.

**Second Pass (Difference Calculation):** We iterate forward from the beginning of the `nums` array. We use another `HashSet` to count distinct elements in the prefix `nums[0...i]` as we go. For each index `i`, the prefix count is the current size of our set, and the suffix count is readily available from our pre-computed array at `suffixDistinctCount[i+1]`. We can then compute `diff[i]`.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] distinctDifferenceArray(int[] nums) {
        int n = nums.length;
        int[] diff = new int[n];

        // Pass 1: Pre-calculate distinct counts for all suffixes
        int[] suffixDistinctCount = new int[n + 1];
        Set<Integer> suffixSet = new HashSet<>();
        suffixDistinctCount[n] = 0; // Empty suffix has 0 distinct elements
        for (int i = n - 1; i >= 0; i--) {
            suffixSet.add(nums[i]);
            suffixDistinctCount[i] = suffixSet.size();
        }

        // Pass 2: Calculate prefix distinct counts and the difference array
        Set<Integer> prefixSet = new HashSet<>();
        for (int i = 0; i < n; i++) {
            prefixSet.add(nums[i]);
            int prefixCount = prefixSet.size();
            int suffixCount = suffixDistinctCount[i + 1];
            diff[i] = prefixCount - suffixCount;
        }

        return diff;
    }
}
```
### Algorithm
- Create an integer array `suffixDistinctCount` of size `n+1`.
- Create a `HashSet<Integer>` `set`.
- For `i` from `n-1` down to `0`:
  - Add `nums[i]` to `set`.
  - `suffixDistinctCount[i] = set.size()`.
- Set `suffixDistinctCount[n] = 0` for the empty suffix.
- Create an integer array `diff` of size `n`.
- Clear the `set` (or create a new one for prefixes).
- For `i` from `0` to `n-1`:
  - Add `nums[i]` to the prefix `set`.
  - `diff[i] = set.size() - suffixDistinctCount[i+1]`.
- Return `diff`.

## Optimized Single-Pass Approach
This is a highly optimized approach that calculates the distinct difference array in a single pass over the input array after an initial frequency count of all elements. It cleverly maintains the counts of distinct elements in the prefix and suffix as it iterates by treating the current element `nums[i]` as moving from the suffix part to the prefix part.
**Time:** O(n). We have an initial pass to build the frequency map which takes `O(n)`. The main loop then runs `n` times, with constant time operations inside (array access). Total time is `O(n) + O(n) = O(n)`. · **Space:** O(n) for the output array. The auxiliary space is O(1) because the frequency maps `prefixFreq` and `suffixFreq` have a fixed size of 51, which is constant and does not depend on `n`. If the range of numbers were unbounded, the space would be `O(k)` where `k` is the number of distinct elements.
**Pros:** Highly efficient with `O(n)` time complexity.; Constant auxiliary space (`O(1)`) due to the constraints on the values in `nums`, making it very memory-efficient.; Processes the array in a single main pass after an initial setup.
**Cons:** The logic is slightly more complex to reason about compared to the two-pass approach.; Requires an initial pass to build the frequency map before the main processing loop.
### Explanation
This approach achieves `O(n)` time complexity with a single main pass and `O(1)` auxiliary space (thanks to the problem constraints). 

First, we perform an initial scan to populate a frequency map of all numbers in the array. This gives us the total count of each number. The number of unique keys in this map is our initial `suffixDistinctCount` (for an empty prefix before `i=0`).

Then, we iterate through the `nums` array from `i = 0` to `n-1`. In each step, we update the prefix and suffix counts:
- **Prefix Update**: We add `nums[i]` to the prefix. We use a separate prefix frequency map. If `nums[i]` is seen for the first time in the prefix, we increment our `prefixDistinctCount`.
- **Suffix Update**: Since `nums[i]` is now part of the prefix, it's no longer in the suffix `nums[i+1...n-1]`. We decrement its count in our initial (suffix) frequency map. If its count drops to zero, it means this number is now completely exhausted from the suffix, so we decrement `suffixDistinctCount`.

After updating both counts, we calculate `diff[i] = prefixDistinctCount - suffixDistinctCount`.

Due to the constraint `1 <= nums[i] <= 50`, we can use simple arrays of size 51 as frequency maps instead of `HashMap`s for better performance.

```java
class Solution {
    public int[] distinctDifferenceArray(int[] nums) {
        int n = nums.length;
        int[] diff = new int[n];
        
        // Using arrays as frequency maps due to constraints (1 <= nums[i] <= 50)
        int[] prefixFreq = new int[51];
        int[] suffixFreq = new int[51];
        
        int suffixDistinctCount = 0;
        for (int num : nums) {
            if (suffixFreq[num] == 0) {
                suffixDistinctCount++;
            }
            suffixFreq[num]++;
        }
        
        int prefixDistinctCount = 0;
        for (int i = 0; i < n; i++) {
            int currentNum = nums[i];
            
            // Update prefix count as we see a new element
            if (prefixFreq[currentNum] == 0) {
                prefixDistinctCount++;
            }
            prefixFreq[currentNum]++;
            
            // Update suffix count as we consume an element
            suffixFreq[currentNum]--;
            if (suffixFreq[currentNum] == 0) {
                suffixDistinctCount--;
            }
            
            diff[i] = prefixDistinctCount - suffixDistinctCount;
        }
        
        return diff;
    }
}
```
### Algorithm
- Create a frequency map `suffixFreq` for all elements in `nums` (an array of size 51 works due to constraints).
- Initialize `suffixDistinctCount` to the number of unique elements in `suffixFreq`.
- Create an empty frequency map `prefixFreq`.
- Initialize `prefixDistinctCount = 0`.
- Create an integer array `diff` of size `n`.
- For `i` from `0` to `n-1`:
  - // Update prefix
  - Increment `prefixFreq[nums[i]]`.
  - If `prefixFreq[nums[i]] == 1`, increment `prefixDistinctCount`.
  - // Update suffix
  - Decrement `suffixFreq[nums[i]]`.
  - If `suffixFreq[nums[i]] == 0`, decrement `suffixDistinctCount`.
  - // Store result
  - `diff[i] = prefixDistinctCount - suffixDistinctCount`.
- Return `diff`.

# Solutions
### Java

```java
class Solution {
public
  int[] distinctDifferenceArray(int[] nums) {
    int n = nums.length;
    int[] suf = new int[n + 1];
    Set<Integer> s = new HashSet<>();
    for (int i = n - 1; i >= 0; --i) {
      s.add(nums[i]);
      suf[i] = s.size();
    }
    s.clear();
    int[] ans = new int[n];
    for (int i = 0; i < n; ++i) {
      s.add(nums[i]);
      ans[i] = s.size() - suf[i + 1];
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> distinctDifferenceArray(vector<int> &nums) {
    int n = nums.size();
    vector<int> suf(n + 1);
    unordered_set<int> s;
    for (int i = n - 1; i >= 0; --i) {
      s.insert(nums[i]);
      suf[i] = s.size();
    }
    s.clear();
    vector<int> ans(n);
    for (int i = 0; i < n; ++i) {
      s.insert(nums[i]);
      ans[i] = s.size() - suf[i + 1];
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def distinctDifferenceArray(self, nums: List[int]) -> List[int]: n = len(nums) ans = [0] * n for i in range(n): a = len(set(nums[: i + 1])) b = len(set(nums[i + 1:])) ans[i] = a - b return ans

```