Skip to content

2670. Find the Distinct Difference Array 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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