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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Distinct Difference Array

Number: 2777

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given a 0-indexed array nums of length n, we want to compute an array diff where diff[i] is the difference between the number of distinct elements in the prefix nums[0...i] and the number of distinct elements in the suffix nums[i+1...n-1]. For cases where the suffix is empty (i.e. when i is the last index), consider its distinct count as 0.

Key Insights

  • We can precompute the number of distinct elements in the prefix for each index by iterating from left to right while maintaining a set.
  • Similarly, we compute the distinct count for the suffix by iterating from right to left and using a set.
  • For each index i, the answer is simply prefix_distinct_count[i] minus (suffix_distinct_count[i+1] if i+1 exists, otherwise 0).

Space and Time Complexity

Time Complexity: O(n), where n is the length of the array (each element is processed twice). Space Complexity: O(n) for storing the prefix and suffix counts, plus O(k) for the sets (with k ≤ n).

Solution

We solve the problem by performing two passes over the array. First, we traverse the array from the beginning to calculate, for every index, the total number of distinct elements encountered in the prefix. Then, we perform a reverse traversal to calculate the number of distinct elements in the suffix (from i+1 to end). Finally, we compute the difference between these two values for every index i to form the distinct difference array. The use of sets to track distinct elements ensures that we count each unique element only once.

Code Solutions

# Python solution

def distinctDifferenceArray(nums):
    n = len(nums)
    prefix_distinct = [0] * n     # Array to store distinct counts in prefix
    suffix_distinct = [0] * (n + 1) # Array to store distinct counts in suffix (n+1 size for convenience)
    
    seen_prefix = set()
    # Calculate prefix distinct counts
    for i in range(n):
        seen_prefix.add(nums[i])
        prefix_distinct[i] = len(seen_prefix)
    
    seen_suffix = set()
    # Calculate suffix distinct counts from the end
    # suffix_distinct[i] will hold the distinct count for nums[i:n]
    for i in range(n - 1, -1, -1):
        seen_suffix.add(nums[i])
        suffix_distinct[i] = len(seen_suffix)
    
    # Build the result array using the precomputed counts
    result = []
    for i in range(n):
        # For index i, suffix distinct count is taken from index i+1 (if exists)
        suffix_count = suffix_distinct[i + 1] if i + 1 < n + 1 else 0
        result.append(prefix_distinct[i] - suffix_count)
    
    return result

# Example usage:
nums = [3,2,3,4,2]
print(distinctDifferenceArray(nums))  # Expected Output: [-2, -1, 0, 2, 3]
← Back to All Questions