Find the Distinct Difference Array

easy array hash set prefix sum

Problem

You are given a 0-indexed array nums of length n. The distinct difference array diff has the same length, where diff[i] equals the number of distinct elements in the prefix nums[0..i] minus the number of distinct elements in the suffix nums[i+1..n-1]. Return diff.

Inputnums = [1,2,3,4,5]

Output[-3,-1,1,3,5]

At i=0: prefix {1} has 1 distinct, suffix {2,3,4,5} has 4, so 1 − 4 = −3.

nums

def distinct_difference_array(nums):
    n = len(nums)
    suffix = [0] * (n + 1)
    seen = set()
    for i in range(n - 1, -1, -1):
        seen.add(nums[i])
        suffix[i] = len(seen)
    diff = [0] * n
    prefix = set()
    for i in range(n):
        prefix.add(nums[i])
        diff[i] = len(prefix) - suffix[i + 1]
    return diff

function distinctDifferenceArray(nums) {
  const n = nums.length;
  const suffix = new Array(n + 1).fill(0);
  const seen = new Set();
  for (let i = n - 1; i >= 0; i--) {
    seen.add(nums[i]);
    suffix[i] = seen.size;
  }
  const diff = new Array(n).fill(0);
  const prefix = new Set();
  for (let i = 0; i < n; i++) {
    prefix.add(nums[i]);
    diff[i] = prefix.size - suffix[i + 1];
  }
  return diff;
}

class Solution {
    public int[] distinctDifferenceArray(int[] nums) {
        int n = nums.length;
        int[] suffix = new int[n + 1];
        Set<Integer> seen = new HashSet<>();
        for (int i = n - 1; i >= 0; i--) {
            seen.add(nums[i]);
            suffix[i] = seen.size();
        }
        int[] diff = new int[n];
        Set<Integer> prefix = new HashSet<>();
        for (int i = 0; i < n; i++) {
            prefix.add(nums[i]);
            diff[i] = prefix.size() - suffix[i + 1];
        }
        return diff;
    }
}

vector<int> distinctDifferenceArray(vector<int>& nums) {
    int n = nums.size();
    vector<int> suffix(n + 1, 0);
    unordered_set<int> seen;
    for (int i = n - 1; i >= 0; i--) {
        seen.insert(nums[i]);
        suffix[i] = seen.size();
    }
    vector<int> diff(n);
    unordered_set<int> prefix;
    for (int i = 0; i < n; i++) {
        prefix.insert(nums[i]);
        diff[i] = (int)prefix.size() - suffix[i + 1];
    }
    return diff;
}

Explanation

For every index i we need two distinct-counts: how many unique values appear in the prefix nums[0..i] and how many appear in the suffix nums[i+1..n-1]. The answer at i is the prefix count minus the suffix count.

Counting distinct values from scratch for each i would be slow. Instead we precompute the suffix counts in one right-to-left pass: walking backward and inserting into a set, suffix[i] records how many distinct values lie from i to the end.

Then we sweep left to right with a second set for the prefix. After adding nums[i], the set size is the prefix distinct count, and the suffix distinct count for the part after i is just the precomputed suffix[i+1]. Subtract and store.

Using sets makes “distinct” trivial: duplicates collapse automatically, so the size is always the number of unique elements seen so far. The two precomputed structures let us answer each index in constant time.

Example: [1,2,3,4,5]. Suffix distinct counts are [5,4,3,2,1,0]. Prefix sizes grow 1,2,3,4,5. So diff = [1-4, 2-3, 3-2, 4-1, 5-0] = [-3,-1,1,3,5].

Time: O(n) Space: O(n)