Find the Distinct Difference Array — Problem & Solution
Find the Distinct Difference Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Find the Distinct Difference Array is an easy coding problem on arrays, hash table and prefix sum, asked in Amazon and Wipro interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table, Prefix Sum
- Asked at: Amazon, Wipro
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
For a 0-indexed array nums of length n, the distinct difference array diff also has length n, and
diff[i] = (number of distinct values in the prefix nums[0..i]) − (number of distinct values in the suffix nums[i+1..n-1]).
An empty suffix contributes 0. Return diff.
Example 1
Input: nums = [1,2,3,4,5]
Output: [-3,-1,1,3,5]
Explanation: At i = 0 the prefix has 1 distinct value and the suffix has 4, so diff[0] = 1 - 4 = -3.
Example 2
Input: nums = [3,2,3,4,2]
Output: [-2,-1,0,2,3]
Explanation: At i = 2 the prefix {3,2} has 2 distinct values and the suffix {4,2} has 2, so diff[2] = 0.
Example 3
Input: nums = [7]
Output: [1]
Explanation: The suffix is empty.
Constraints
1 <= nums.length <= 501 <= nums[i] <= 50
Hints for Find the Distinct Difference Array
Hint 1
Two quantities per index: distinct in the prefix, distinct in the suffix.
Hint 2
One right-to-left pass can precompute every suffix count into an array.
Hint 3
Then a left-to-right pass grows the prefix set and subtracts the precomputed suffix count.
How to solve Find the Distinct Difference Array
The two halves move in opposite directions, so precompute one of them. A right-to-left pass records how many distinct values sit strictly after each index; a left-to-right pass then grows the prefix set and subtracts.
Approach
- Sweep
ifromn - 1down to0, insertingnums[i]into a set after recordingsufCount[i]— the size of the set coveringnums[i+1..]. - Sweep
ifrom0upward, insertingnums[i]into a second set first, so its size is the prefix distinct count fornums[0..i]. - Write
diff[i] = prefixSize - sufCount[i].
Why it works
Each pass maintains exactly the set the definition names, and because a set is inserted into before (or after) the read in the right order, the count read at index i covers precisely the half the statement describes.
Complexity
- Time —
O(n) with hashing — the O(n²) recount also passes at these limits - Space —
O(n)
Pitfalls
- Recording the suffix count after inserting
nums[i]includesnums[i]itself, which the definition excludes. - The last suffix is empty and must contribute
0, not1.
Reference solution
Python
from typing import List
def distinctDifferenceArray(nums: List[int]) -> List[int]:
n = len(nums)
suf = [0] * (n + 1)
seen = set()
for i in range(n - 1, -1, -1):
suf[i] = len(seen)
seen.add(nums[i])
out = []
pre = set()
for i in range(n):
pre.add(nums[i])
out.append(len(pre) - suf[i])
return outJava
public static int[] distinctDifferenceArray(int[] nums) {
int n = nums.length;
int[] suf = new int[n + 1];
Set<Integer> seen = new HashSet<>();
for (int i = n - 1; i >= 0; i--) {
suf[i] = seen.size();
seen.add(nums[i]);
}
int[] out = new int[n];
Set<Integer> pre = new HashSet<>();
for (int i = 0; i < n; i++) {
pre.add(nums[i]);
out[i] = pre.size() - suf[i];
}
return out;
}C++
vector<int> distinctDifferenceArray(vector<int>& nums) {
int n = (int) nums.size();
vector<int> suf(n + 1, 0);
unordered_set<int> seen;
for (int i = n - 1; i >= 0; i--) {
suf[i] = (int) seen.size();
seen.insert(nums[i]);
}
vector<int> out(n);
unordered_set<int> pre;
for (int i = 0; i < n; i++) {
pre.insert(nums[i]);
out[i] = (int) pre.size() - suf[i];
}
return out;
}JavaScript
var distinctDifferenceArray = function(nums) {
var n = nums.length;
var suf = [];
for (var t = 0; t <= n; t++) suf.push(0);
var seen = {}, sc = 0;
for (var i = n - 1; i >= 0; i--) {
suf[i] = sc;
if (seen[String(nums[i])] !== true) { seen[String(nums[i])] = true; sc++; }
}
var out = [], pre = {}, pc = 0;
for (var j = 0; j < n; j++) {
if (pre[String(nums[j])] !== true) { pre[String(nums[j])] = true; pc++; }
out.push(pc - suf[j]);
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets