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 <= 501 <= nums[i] <= 50Problem Overview: You are given an integer array nums. For every index i, compute the number of distinct values in the prefix nums[0..i] and subtract the number of distinct values in the suffix nums[i+1..n-1]. The result for each position forms the distinct difference array.
Approach 1: Prefix and Suffix Sets with Iteration (O(n) time, O(n) space)
Track distinct counts from both directions using hash sets. First iterate from right to left and maintain a set of seen values to compute a suffixDistinct[i] array representing the number of unique elements in nums[i..n-1]. Then iterate left to right with another set for the prefix. At index i, the prefix distinct count is the size of the prefix set, and the suffix count is suffixDistinct[i+1]. Subtract them and store the result. Hash set insertions and lookups are O(1) on average, so the full pass remains linear.
This approach directly models the problem definition and is easy to reason about during interviews. It relies on fast membership checks provided by a hash table and sequential iteration over the array.
Approach 2: Optimized Prefix and Suffix Tracking with Arrays (O(n + k) time, O(k) space)
Since the value range is small, you can replace hash sets with fixed-size frequency arrays. Maintain a suffix frequency array and a counter tracking how many distinct elements remain in the suffix. As you iterate from left to right, decrease the frequency of the current element in the suffix structure and update the suffix distinct counter when a frequency drops to zero. At the same time, maintain a prefix frequency array and increment the prefix distinct counter the first time a value appears.
Each index performs constant-time updates to the two frequency arrays and adjusts the distinct counters. This avoids hash structures entirely and gives predictable memory usage. The algorithm still scans the array once while performing simple frequency updates, a common pattern in counting problems and prefix-style array processing.
Recommended for interviews: The hash set prefix/suffix approach is the most intuitive and usually what interviewers expect first. It clearly shows that you understand how to track distinct elements efficiently. The frequency-array optimization demonstrates deeper awareness of constraints and memory tradeoffs, which can help you stand out once the baseline solution is established.
This approach involves iterating through the array twice. Once from the right to left to compute suffix distinct element counts and store them in an auxiliary array. Then, iterate from left to right to compute prefix distinct counts and calculate the difference using the precomputed suffix array.
We utilize two sets to keep track of distinct elements in the prefix and suffix sections of the array. The suffix distinct counts are precomputed in a separate array by iterating backwards. Then, during a forward iteration, we update the prefix distinct count and compute the distinct difference based on the suffix counts.
Time complexity is O(n), where n is the number of elements in the array, as we iterate through the array multiple times. Space complexity is also O(n) due to the usage of additional arrays and sets.
This approach improves upon the previous method by utilizing arrays to track the presence of distinct elements more efficiently in both prefix and suffix calculations. This eliminates the need for sets, optimizing for scenarios where the element range is constrained.
This C solution leverages arrays to directly track the presence of each unique number. Since the value range is constrained (1 to 50), using direct indexing for presence tracking is efficient.
C
JavaScript
The algorithm achieves a time complexity of O(n) and a space complexity of O(1) for prefix and suffix tracking arrays, disregarding the input and output storage.
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.
| Approach | Complexity |
|---|---|
| Prefix and Suffix Sets with Iteration | Time complexity is O(n), where n is the number of elements in the array, as we iterate through the array multiple times. Space complexity is also O(n) due to the usage of additional arrays and sets. |
| Optimized Prefix and Suffix Tracking with Arrays | The algorithm achieves a time complexity of O(n) and a space complexity of O(1) for prefix and suffix tracking arrays, disregarding the input and output storage. |
| Hash Table + Preprocessed Suffix | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix and Suffix Sets with Iteration | O(n) | O(n) | General case. Clear logic using hash sets to track unique elements. |
| Optimized Prefix and Suffix Tracking with Arrays | O(n + k) | O(k) | Best when value range is small and predictable. Avoids hash table overhead. |
Find the Distinct Difference Array | Leetcode 2670 | Weekly Contest 344 • Technosage • 2,468 views views
Watch 9 more video solutions →Practice Find the Distinct Difference Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor