Find the Distinct Difference Array

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 _thedistinct 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.

Examples

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

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

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

Code

C++

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

Go

func distinctDifferenceArray(nums []int) []int {
    n := len(nums)
    pre := make([]int, n)
    suf := make([]int, n)
    ans := make([]int, n)
    s := map[int]struct{}{}
    for i := 0; i < n; i++ {
        s[nums[i]] = struct{}{}
        pre[i] = len(s)
    }
    s = map[int]struct{}{}
    for i := n-1; i >= 0; i-- {
        suf[i] = len(s)
        s[nums[i]] = struct{}{}
    }
    for i := 0; i < n; i++ {
        ans[i] = pre[i] - suf[i]
    }
    return ans
}

Java

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

Kotlin

class Solution {
    fun distinctDifferenceArray(nums: IntArray): IntArray {
        val n = nums.size
        val pre = IntArray(n)
        val suf = IntArray(n)
        val ans = IntArray(n)
        val s = mutableSetOf<Int>()
        for (i in 0 until n) {
            s.add(nums[i])
            pre[i] = s.size
        }
        s.clear()
        for (i in n-1 downTo 0) {
            suf[i] = s.size
            s.add(nums[i])
        }
        for (i in 0 until n) ans[i] = pre[i] - suf[i]
        return ans
    }
}

Python

class Solution:
    def distinctDifferenceArray(self, nums: list[int]) -> list[int]:
        n = len(nums)
        pre, suf, ans = [0]*n, [0]*n, [0]*n
        s = set()
        for i in range(n):
            s.add(nums[i])
            pre[i] = len(s)
        s.clear()
        for i in range(n-1, -1, -1):
            suf[i] = len(s)
            s.add(nums[i])
        for i in range(n):
            ans[i] = pre[i] - suf[i]
        return ans

Rust

use std::collections::HashSet;
impl Solution {
    pub fn distinct_difference_array(nums: Vec<i32>) -> Vec<i32> {
        let n = nums.len();
        let mut pre = vec![0; n];
        let mut suf = vec![0; n];
        let mut ans = vec![0; n];
        let mut s = HashSet::new();
        for i in 0..n {
            s.insert(nums[i]);
            pre[i] = s.len() as i32;
        }
        s.clear();
        for i in (0..n).rev() {
            suf[i] = s.len() as i32;
            s.insert(nums[i]);
        }
        for i in 0..n {
            ans[i] = pre[i] - suf[i];
        }
        ans
    }
}

TypeScript

class Solution {
    distinctDifferenceArray(nums: number[]): number[] {
        const n = nums.length, pre = Array(n).fill(0), suf = Array(n).fill(0), ans = Array(n).fill(0);
        const s = new Set<number>();
        for (let i = 0; i < n; ++i) {
            s.add(nums[i]);
            pre[i] = s.size;
        }
        s.clear();
        for (let i = n-1; i >= 0; --i) {
            suf[i] = s.size;
            s.add(nums[i]);
        }
        for (let i = 0; i < n; ++i) ans[i] = pre[i] - suf[i];
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n), as each element is processed twice.
• 🧺 Space complexity: O(n), for the prefix, suffix, and answer arrays.