algoadvance

Leetcode 2670. Find the Distinct Difference Array

Problem Statement

You are given a 0-indexed integer array nums of length n. The distinct difference array of nums is an integer array diff of length n such that diff[i] is equal to the number of distinct elements in the suffix nums[i+1:] minus the number of distinct elements in the prefix nums[0:i+1].

Return the distinct difference array of nums.

Example 1:

Input: nums = [1,2,3,4,5]
Output: [-3,-1,1,3,5]
Explanation: For index i = 0:
- The prefix is [1] and the suffix is [2,3,4,5].
- The count of distinct elements in the prefix is 1 and in the suffix is 4.
Thus, diff[0] = 4 - 1 = 3.

Example 2:

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

Clarifying Questions

  1. Can the length of the array nums be zero?
    • No, the array nums will have at least one element.
  2. Are there any constraints on the values within nums?
    • No specific constraints were given, so we assume typical constraints for an integer array.
  3. Should we return the result in a new array or modify the given array?
    • We should return the result in a new array.

Strategy

  1. Initial Setup:
    • We will use sets to store distinct elements for prefixes and suffixes.
  2. Prefix Calculation:
    • Use a set to maintain and count distinct elements as we iterate through the prefix of the array.
  3. Suffix Calculation:
    • Use another set to precompute distinct element counts for all suffixes starting from each index.
  4. Compute the Result:
    • Iterate through the array and use the precomputed prefix and suffix distinct counts to fill the result array diff.

Code

Here is the C++ implementation of the solution:

#include <vector>
#include <unordered_set>
#include <iostream>

std::vector<int> distinctDifferenceArray(const std::vector<int>& nums) {
    int n = nums.size();
    std::vector<int> diff(n);

    // Using unordered_set to track distinct elements
    std::unordered_set<int> prefixSet, suffixSet;
    std::vector<int> suffixDistinctCount(n, 0);

    // Building distinct count for suffixes
    for (int i = n - 1; i >= 0; --i) {
        suffixSet.insert(nums[i]);
        suffixDistinctCount[i] = suffixSet.size();
    }

    // Calculating the distinct difference array
    for (int i = 0; i < n; ++i) {
        prefixSet.insert(nums[i]);
        int prefixCount = prefixSet.size();
        int suffixCount = (i + 1 < n) ? suffixDistinctCount[i + 1] : 0;
        diff[i] = suffixCount - prefixCount;
    }

    return diff;
}

// For testing
int main() {
    std::vector<int> nums1 = {1, 2, 3, 4, 5};
    std::vector<int> result1 = distinctDifferenceArray(nums1);
    for (int val : result1) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    std::vector<int> nums2 = {3, 2, 3, 4, 2};
    std::vector<int> result2 = distinctDifferenceArray(nums2);
    for (int val : result2) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}

Time Complexity

Overall, the time complexity of this solution is (O(n)).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI