Description

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.

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

/**
 * @param {number[]} nums
 * @return {number[]}
 */
const countDistinct = (map) => {
    return [...map.entries()]?.filter(([key,value]) => value!==0).length
}
var distinctDifferenceArray = function(nums) {
    const leftMap = new Map() 
    const rightMap = new Map()
    let diff=[]
    nums.forEach((num) => {
        if(!rightMap.has(num)){
            rightMap.set(num,1)
        }else{
            rightMap.set(num, rightMap.get(num)+1)
        }
    })
    nums.forEach((num) => {
        if(!leftMap.has(num)){
            leftMap.set(num,1)
        }
        rightMap.set(num, rightMap.get(num)-1)
        const countLeft = leftMap.size
        const countRight = countDistinct(rightMap)
        diff.push(countLeft-countRight)
    })
    return diff
};