#2670

Find the Distinct Difference Array

newbie · 215 · lc easy +17 · verified · 77.1% accepted · 369 likes · top 88%

Description

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

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.

Code

1

2

3

class Solution:
    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:

class Solution:
    def distinctDifferenceArray(self, nums: List[int]) -> List[int]: