Practice/Google/Leetcode 2670. Find the Distinct Difference Array

Leetcode 2670. Find the Distinct Difference Array

CodingOptional

Problem

You are given an integer array nums. For each index i in the array, you need to calculate a difference value based on distinct elements.

For each position i, compute:

• The number of distinct elements in the prefix subarray nums[0] through nums[i] (inclusive)
• The number of distinct elements in the suffix subarray nums[i+1] through nums[n-1] (inclusive)

Return an array result where result[i] equals the difference: (distinct count in prefix) minus (distinct count in suffix).

Requirements

1. Create an array of the same length as the input
2. For each index, calculate the count of unique elements before and including that index
3. For each index, calculate the count of unique elements after that index
4. Return the difference (prefix count - suffix count) for each position
5. Handle edge cases where the suffix is empty (last element)

Constraints

• 1 ≤ nums.length ≤ 50
• 1 ≤ nums[i] ≤ 50
• Time complexity should be O(n) where n is the length of the array
• Space complexity should be O(n) for tracking distinct elements

Examples

Example 1:

` Input: nums = [1, 2, 3, 4, 5] Output: [-3, -1, 1, 3, 5] Explanation:

• Index 0: prefix {1} has 1 distinct, suffix {2,3,4,5} has 4 distinct → 1-4 = -3
• Index 1: prefix {1,2} has 2 distinct, suffix {3,4,5} has 3 distinct → 2-3 = -1
• Index 2: prefix {1,2,3} has 3 distinct, suffix {4,5} has 2 distinct → 3-2 = 1
• Index 3: prefix {1,2,3,4} has 4 distinct, suffix {5} has 1 distinct → 4-1 = 3
• Index 4: prefix {1,2,3,4,5} has 5 distinct, suffix {} has 0 distinct → 5-0 = 5 `

Example 2:

` Input: nums = [3, 2, 3, 4, 2] Output: [-2, -1, 0, 2, 3] Explanation:

• Index 0: prefix {3} has 1 distinct, suffix {2,3,4,2} has 3 distinct → 1-3 = -2
• Index 1: prefix {3,2} has 2 distinct, suffix {3,4,2} has 3 distinct → 2-3 = -1
• Index 2: prefix {3,2,3} has 2 distinct, suffix {4,2} has 2 distinct → 2-2 = 0
• Index 3: prefix {3,2,3,4} has 3 distinct, suffix {2} has 1 distinct → 3-1 = 2
• Index 4: prefix {3,2,3,4,2} has 3 distinct, suffix {} has 0 distinct → 3-0 = 3 `

Example 3:

Input: nums = [5] Output: [1] Explanation: Only one element. Prefix has 1 distinct, suffix is empty (0 distinct) → 1-0 = 1