We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find the Distinct Difference Array

Difficulty: Easy

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

Key Insights

  • The problem requires calculating distinct counts in both prefix and suffix for each index.
  • A hash set can be used to track distinct elements efficiently.
  • The constraints allow for a straightforward approach, as the maximum size of the array is small (up to 50).

Space and Time Complexity

Time Complexity: O(n^2) - for each index, we may need to traverse the prefix and suffix. Space Complexity: O(n) - for storing distinct elements in a set.

Solution

To solve the problem, we will use a two-pass approach with hash sets:

  1. In the first pass, compute the distinct counts for the prefix for each index.
  2. In the second pass, compute the distinct counts for the suffix and calculate the difference using the prefix counts.

We will utilize hash sets to keep track of distinct elements as we process the array.

Code Solutions

def distinctDifferenceArray(nums):
    n = len(nums)
    diff = [0] * n
    prefix_set = set()
    
    # Calculate distinct counts for prefixes
    prefix_counts = []
    for i in range(n):
        prefix_set.add(nums[i])
        prefix_counts.append(len(prefix_set))
    
    suffix_set = set()
    
    # Calculate distinct counts for suffixes and populate diff
    for i in range(n-1, -1, -1):
        if i < n - 1:
            suffix_set.add(nums[i + 1])
        diff[i] = prefix_counts[i] - len(suffix_set)
    
    return diff
← Back to All Questions