Watch 10 video solutions for Find the Distinct Difference Array, a easy level problem involving Array, Hash Table. This walkthrough by Technosage has 2,468 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |