LeetCode 2670. Find the Distinct Difference Array Solution in Java, C++, Python & More | Explanation + Code

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.

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

Solutions

Solution 1: Hash Table + Preprocessed Suffix

We can preprocess a suffix array suf, where suf[i] represents the number of distinct elements in the suffix nums[i, ..., n - 1]. During the preprocessing, we use a hash table s to maintain the elements that have appeared in the suffix, so we can query the number of distinct elements in the suffix in O(1) time.

After preprocessing the suffix array suf, we clear the hash table s, and then traverse the array nums again, using the hash table s to maintain the elements that have appeared in the prefix. The answer at position i is the number of distinct elements in s minus suf[i + 1], that is, s.size() - suf[i + 1].

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.

PythonJavaC++GoTypeScriptRust

class Solution: def distinctDifferenceArray(self, nums: List[int]) -> List[int]: n = len(nums) suf = [0] * (n + 1) s = set() for i in range(n - 1, -1, -1): s.add(nums[i]) suf[i] = len(s) s.clear() ans = [0] * n for i, x in enumerate(nums): s.add(x) ans[i] = len(s) - suf[i + 1] return ans(code-box)

class Solution { public int[] distinctDifferenceArray(int[] nums) { int n = nums.length; int[] suf = new int[n + 1]; Set<Integer> s = new HashSet<>(); for (int i = n - 1; i >= 0; --i) { s.add(nums[i]); suf[i] = s.size(); } s.clear(); int[] ans = new int[n]; for (int i = 0; i < n; ++i) { s.add(nums[i]); ans[i] = s.size() - suf[i + 1]; } return ans; } }(code-box)

class Solution { public: vector<int> distinctDifferenceArray(vector<int>& nums) { int n = nums.size(); vector<int> suf(n + 1); unordered_set<int> s; for (int i = n - 1; i >= 0; --i) { s.insert(nums[i]); suf[i] = s.size(); } s.clear(); vector<int> ans(n); for (int i = 0; i < n; ++i) { s.insert(nums[i]); ans[i] = s.size() - suf[i + 1]; } return ans; } };(code-box)

func distinctDifferenceArray(nums []int) []int { n := len(nums) suf := make([]int, n+1) s := map[int]bool{} for i := n - 1; i >= 0; i-- { s[nums[i]] = true suf[i] = len(s) } ans := make([]int, n) s = map[int]bool{} for i, x := range nums { s[x] = true ans[i] = len(s) - suf[i+1] } return ans }(code-box)

function distinctDifferenceArray(nums: number[]): number[] { const n = nums.length; const suf: number[] = Array(n + 1).fill(0); const s: Set<number> = new Set(); for (let i = n - 1; i >= 0; --i) { s.add(nums[i]); suf[i] = s.size; } s.clear(); const ans: number[] = Array(n).fill(0); for (let i = 0; i < n; ++i) { s.add(nums[i]); ans[i] = s.size - suf[i + 1]; } return ans; }(code-box)

use std::collections::HashSet; impl Solution { pub fn distinct_difference_array(nums: Vec<i32>) -> Vec<i32> { let n = nums.len(); let mut suf = vec![0; n + 1]; let mut s = HashSet::new(); for i in (0..n).rev() { s.insert(nums[i]); suf[i] = s.len(); } let mut ans = Vec::new(); s.clear(); for i in 0..n { s.insert(nums[i]); ans.push((s.len() - suf[i + 1]) as i32); } ans } }(code-box)