2670. Find the Distinct Difference Array LeetCode Solution

In this guide, you will get 2670. Find the Distinct Difference Array LeetCode Solution with the best time and space complexity. The solution to Find the Distinct Difference Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Find the Distinct Difference Array solution in C++
Find the Distinct Difference Array solution in Java
Find the Distinct Difference Array solution in Python
Additional Resources

2670. Find the Distinct Difference Array LeetCode Solution image

Problem Statement of Find the Distinct Difference Array

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.
Note that nums[i, …, j] denotes the subarray of nums starting at index i and ending at index j inclusive. Particularly, if i > j then nums[i, …, j] denotes an empty subarray.

Example 1:

Input: nums = [1,2,3,4,5]
Output: [-3,-1,1,3,5]
Explanation: For index i = 0, there is 1 element in the prefix and 4 distinct elements in the suffix. Thus, diff[0] = 1 – 4 = -3.
For index i = 1, there are 2 distinct elements in the prefix and 3 distinct elements in the suffix. Thus, diff[1] = 2 – 3 = -1.
For index i = 2, there are 3 distinct elements in the prefix and 2 distinct elements in the suffix. Thus, diff[2] = 3 – 2 = 1.
For index i = 3, there are 4 distinct elements in the prefix and 1 distinct element in the suffix. Thus, diff[3] = 4 – 1 = 3.
For index i = 4, there are 5 distinct elements in the prefix and no elements in the suffix. Thus, diff[4] = 5 – 0 = 5.

Example 2:

Input: nums = [3,2,3,4,2]
Output: [-2,-1,0,2,3]
Explanation: For index i = 0, there is 1 element in the prefix and 3 distinct elements in the suffix. Thus, diff[0] = 1 – 3 = -2.
For index i = 1, there are 2 distinct elements in the prefix and 3 distinct elements in the suffix. Thus, diff[1] = 2 – 3 = -1.
For index i = 2, there are 2 distinct elements in the prefix and 2 distinct elements in the suffix. Thus, diff[2] = 2 – 2 = 0.
For index i = 3, there are 3 distinct elements in the prefix and 1 distinct element in the suffix. Thus, diff[3] = 3 – 1 = 2.
For index i = 4, there are 3 distinct elements in the prefix and no elements in the suffix. Thus, diff[4] = 3 – 0 = 3.

Constraints:

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

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

2670. Find the Distinct Difference Array LeetCode Solution in C++

class Solution {
 public:
  vector<int> distinctDifferenceArray(vector<int>& nums) {
    constexpr int kMax = 50;
    vector<int> ans;
    vector<int> prefixCount(kMax + 1);
    vector<int> suffixCount(kMax + 1);
    int distinctPrefix = 0;
    int distinctSuffix = 0;

    for (const int num : nums)
      if (++suffixCount[num] == 1)
        ++distinctSuffix;

    for (const int num : nums) {
      if (++prefixCount[num] == 1)
        ++distinctPrefix;
      if (--suffixCount[num] == 0)
        --distinctSuffix;
      ans.push_back(distinctPrefix - distinctSuffix);
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

2670. Find the Distinct Difference Array LeetCode Solution in Java

class Solution {
  public int[] distinctDifferenceArray(int[] nums) {
    final int kMax = 50;
    int[] ans = new int[nums.length];
    int[] prefixCount = new int[kMax + 1];
    int[] suffixCount = new int[kMax + 1];
    int distinctPrefix = 0;
    int distinctSuffix = 0;

    for (final int num : nums)
      if (++suffixCount[num] == 1)
        ++distinctSuffix;

    for (int i = 0; i < nums.length; ++i) {
      if (++prefixCount[nums[i]] == 1)
        ++distinctPrefix;
      if (--suffixCount[nums[i]] == 0)
        --distinctSuffix;
      ans[i] = distinctPrefix - distinctSuffix;
    }

    return ans;
  }
}
// code provided by PROGIEZ

2670. Find the Distinct Difference Array LeetCode Solution in Python

class Solution:
  def distinctDifferenceArray(self, nums: list[int]) -> list[int]:
    kMax = 50
    ans = []
    prefixCount = [0] * (kMax + 1)
    suffixCount = [0] * (kMax + 1)
    distinctPrefix = 0
    distinctSuffix = 0

    for num in nums:
      if suffixCount[num] == 0:
        distinctSuffix += 1
      suffixCount[num] += 1

    for num in nums:
      if prefixCount[num] == 0:
        distinctPrefix += 1
      prefixCount[num] += 1
      if suffixCount[num] == 1:
        distinctSuffix -= 1
      suffixCount[num] -= 1
      ans.append(distinctPrefix - distinctSuffix)

    return ans
 # code by PROGIEZ