Find the Distinct Difference Array

Difficulty: Easy | Acceptance: 77.20% | Paid: No Topics: Array, Hash Table

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] equals 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.

• Examples
• Constraints
• Approach 1: Brute Force
• Approach 2: Prefix and Suffix Sets

Examples

Example 1:

Input: nums = [1,2,3,4,5]
Output: [-3,-1,1,3,5]
Explanation: 
- For index 0, the prefix is [1] and the suffix is [2,3,4,5]. There is 1 distinct element in the prefix and 4 distinct elements in the suffix. The difference is 1 - 4 = -3.
- For index 1, the prefix is [1,2] and the suffix is [3,4,5]. There are 2 distinct elements in the prefix and 3 distinct elements in the suffix. The difference is 2 - 3 = -1.
- For index 2, the prefix is [1,2,3] and the suffix is [4,5]. There are 3 distinct elements in the prefix and 2 distinct elements in the suffix. The difference is 3 - 2 = 1.
- For index 3, the prefix is [1,2,3,4] and the suffix is [5]. There are 4 distinct elements in the prefix and 1 distinct element in the suffix. The difference is 4 - 1 = 3.
- For index 4, the prefix is [1,2,3,4,5] and the suffix is []. There are 5 distinct elements in the prefix and 0 distinct elements in the suffix. The difference is 5 - 0 = 5.

Example 2:

Input: nums = [3,2,3,4,2]
Output: [-2,-1,0,2,3]
Explanation: 
- For index 0, the prefix is [3] and the suffix is [2,3,4,2]. There is 1 distinct element in the prefix and 3 distinct elements in the suffix. The difference is 1 - 3 = -2.
- For index 1, the prefix is [3,2] and the suffix is [3,4,2]. There are 2 distinct elements in the prefix and 3 distinct elements in the suffix. The difference is 2 - 3 = -1.
- For index 2, the prefix is [3,2,3] and the suffix is [4,2]. There are 2 distinct elements in the prefix and 2 distinct elements in the suffix. The difference is 2 - 2 = 0.
- For index 3, the prefix is [3,2,3,4] and the suffix is [2]. There are 3 distinct elements in the prefix and 1 distinct element in the suffix. The difference is 3 - 1 = 2.
- For index 4, the prefix is [3,2,3,4,2] and the suffix is []. There are 3 distinct elements in the prefix and 0 distinct elements in the suffix. The difference is 3 - 0 = 3.

Constraints

1 <= n <= 50
1 <= nums[i] <= 50

Approach 1: Brute Force

Intuition Since the constraints are very small ($n \le 50$), we can afford to recalculate the distinct elements for the prefix and suffix at every index from scratch.

Steps

• Iterate through the array from index i = 0 to n-1.
• For each i, create a set from nums[0...i] to get distinct prefix elements.
• Create another set from nums[i+1...n-1] to get distinct suffix elements.
• Calculate the difference between the sizes of these two sets and store it in the result array.

class Solution:
    def distinctDifferenceArray(self, nums: list[int]) -> list[int]:
        n = len(nums)
        res = []
        for i in range(n):
            prefix = set(nums[:i+1])
            suffix = set(nums[i+1:])
            res.append(len(prefix) - len(suffix))
        return res

Complexity

• Time: $O(n²)$
• Space: $O(n)$
• Notes: Simple to implement but inefficient for large inputs.

Approach 2: Prefix and Suffix Sets

Intuition We can optimize the solution by precomputing the number of distinct elements for every prefix and every suffix in a single pass each. This reduces the time complexity to linear.

Steps

• Create a prefix array where prefix[i] stores the count of distinct elements in nums[0...i]. Iterate forward, maintaining a set of seen elements.
• Create a suffix array where suffix[i] stores the count of distinct elements in nums[i...n-1]. Iterate backward, maintaining a set of seen elements.
• Iterate through the array again to calculate the result. For index i, the result is prefix[i] - suffix[i+1]. Handle the edge case where i+1 is out of bounds (suffix is empty, count is 0).

class Solution:
    def distinctDifferenceArray(self, nums: list[int]) -> list[int]:
        n = len(nums)
        prefix = [0] * n
        seen = set()
        for i in range(n):
            seen.add(nums[i])
            prefix[i] = len(seen)
        
        suffix = [0] * (n + 1)
        seen = set()
        for i in range(n - 1, -1, -1):
            suffix[i] = len(seen)
            seen.add(nums[i])
        
        res = []
        for i in range(n):
            res.append(prefix[i] - suffix[i+1])
        return res

Complexity

• Time: $O(n)$
• Space: $O(n)$
• Notes: Optimal time complexity with a trade-off of using extra space for the prefix and suffix arrays.