Find the Distinct Difference Array solution and explanation
9 more videos on this problem
Find the Distinct Difference Array | Leetcode 2670 | Weekly Contest 344Technosage · 13:13 · 2K views
Leetcode | 2670. Find the Distinct Difference Array | Easy | Java SolutionDeveloper Docs · 6:12 · 982 views
Find the Distinct Difference Array Leetcode contest | Weekly Contest 344 FULL(100/100) | AC CodeCodechef Starters 64 · 0:20 · 720 views
LeetCode 2670. Find the Distinct Difference Array - Interview Prep Ep 140Fisher Coder · 9:31 · 705 views
6416. Find the Distinct Difference Array | Leetcode Weekly Contest 344 | Approach | Pseudo Code.Optimization · 1:10 · 561 views
Leetcode 2670. Find the Distinct Difference Array | Weekly Contest 343 | Leetcode weekly contestOffCampus Phodenge | Aman Chowdhury · 10:24 · 493 views
Find the Distinct Difference Array - Leetcode 2670 - PythonAlgorithms Casts · 3:21 · 469 views
Find the Distinct Difference Array Leetcode contest | Weekly Contest 344 FULL(100/100) | AC CodeCodechef Starters 64 · 0:16 · 372 views
2670. Find the Distinct Difference Array (Leetcode Easy)Programming Live with Larry · 2:37 · 286 views
Leetcode 2670 || Find the Distinct Difference Array || Leetcode Weekly Easy || cppKomal Pal · 10:36 · 217 views
The problem
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] <= 50
Approach overview
Problem 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 1: Prefix and Suffix Sets with Iteration
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.
def distinctDifferenceArray(nums):
n = len(nums)
prefix_set = set()
suffix_count = [0] * n
suffix_set = set()
# Calculate suffix count of distinct elements
for i in range(n - 1, -1, -1):
suffix_set.add(nums[i])
suffix_count[i] = len(suffix_set)
result = [0] * n
# Calculate prefix distinct elements and differences
for i in range(n):
prefix_set.add(nums[i])
prefix_count = len(prefix_set)
suffix_count_next = suffix_count[i + 1] if i + 1 < n else 0
result[i] = prefix_count - suffix_count_next
return result
# Example usage:
nums = [3, 2, 3, 4, 2]
print(distinctDifferenceArray(nums)) # Output: [-2, -1, 0, 2, 3]import java.util.HashSet;
import java.util.Set;
public class Main {
public static int[] distinctDifferenceArray(int[] nums) {
int n = nums.length;
int[] suffixCount = new int[n];
Set<Integer> suffixSet = new HashSet<>();
for (int i = n - 1; i >= 0; i--) {
suffixSet.add(nums[i]);
suffixCount[i] = suffixSet.size();
}
Set<Integer> prefixSet = new HashSet<>();
int[] result = new int[n];
for (int i = 0; i < n; i++) {
prefixSet.add(nums[i]);
int prefixCount = prefixSet.size();
int suffixCountNext = (i + 1 < n) ? suffixCount[i + 1] : 0;
result[i] = prefixCount - suffixCountNext;
}
return result;
}
public static void main(String[] args) {
int[] nums = {3, 2, 3, 4, 2};
int[] result = distinctDifferenceArray(nums);
for (int r : result) {
System.out.print(r + " ");
}
}
}using System;
using System.Collections.Generic;
public class Solution {
public int[] DistinctDifferenceArray(int[] nums) {
int n = nums.Length;
int[] suffixCount = new int[n];
HashSet<int> suffixSet = new HashSet<int>();
for (int i = n - 1; i >= 0; i--) {
suffixSet.Add(nums[i]);
suffixCount[i] = suffixSet.Count;
}
HashSet<int> prefixSet = new HashSet<int>();
int[] result = new int[n];
for (int i = 0; i < n; i++) {
prefixSet.Add(nums[i]);
int prefixCount = prefixSet.Count;
int suffixCountNext = (i + 1 < n) ? suffixCount[i + 1] : 0;
result[i] = prefixCount - suffixCountNext;
}
return result;
}
public static void Main(string[] args) {
Solution sol = new Solution();
int[] nums = {3, 2, 3, 4, 2};
int[] result = sol.DistinctDifferenceArray(nums);
foreach (int r in result) {
Console.Write(r + " ");
}
}
}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.
Approach 2: Optimized Prefix and Suffix Tracking with Arrays
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.
function distinctDifferenceArray(nums) {
let n = nums.length;
let suffixCount = new Array(n).fill(0);
let prefixSeen = Array(51).fill(false);
let suffixSeen = Array(51).fill(false);
// Calculate suffix distinct counts
let count = 0;
for (let i = n - 1; i >= 0; i--) {
if (!suffixSeen[nums[i]]) {
suffixSeen[nums[i]] = true;
count++;
}
suffixCount[i] = count;
}
// Calculate prefix distinct counts and differences
let result = new Array(n);
count = 0;
for (let i = 0; i < n; i++) {
if (!prefixSeen[nums[i]]) {
prefixSeen[nums[i]] = true;
count++;
}
let suffix = (i + 1 < n) ? suffixCount[i + 1] : 0;
result[i] = count - suffix;
}
return result;
}
// Example usage:
console.log(distinctDifferenceArray([3, 2, 3, 4, 2])); // Output: [-2, -1, 0, 2, 3]#include <stdio.h>
#include <string.h>
void distinctDifferenceArray(int* nums, int n, int* result) {
int suffixCount[n], prefixSeen[51] = {0};
int suffixSeen[51] = {0};
// Calculate suffix distinct counts
for (int i = 0; i < 51; i++) suffixSeen[i] = 0;
int count = 0;
for (int i = n - 1; i >= 0; i--) {
if (!suffixSeen[nums[i]]) {
suffixSeen[nums[i]] = 1;
count++;
}
suffixCount[i] = count;
}
// Calculate prefix distinct counts and difference
for (int i = 0; i < 51; i++) prefixSeen[i] = 0;
count = 0;
for (int i = 0; i < n; i++) {
if (!prefixSeen[nums[i]]) {
prefixSeen[nums[i]] = 1;
count++;
}
int suffix = (i + 1 < n) ? suffixCount[i + 1] : 0;
result[i] = count - suffix;
}
}
int main() {
int nums[] = {3, 2, 3, 4, 2};
int n = sizeof(nums) / sizeof(nums[0]);
int result[n];
distinctDifferenceArray(nums, n, result);
for (int i = 0; i < n; i++) {
printf("%d ", result[i]);
}
return 0;
}The JavaScript implementation efficiently uses boolean arrays for tracking the presence of distinct numbers, adhering to the bounded range of input values. It adopts a space-efficient approach while maintaining clarity of logic.
The solution operates with a time complexity of O(n) and space complexity of O(1), similar to other efficient implementations.
Approach 3: 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.
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;
}
};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;
}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
}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
}
}Complexity comparison
| 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 solution operates with a time complexity of O(n) and space complexity of O(1), similar to other efficient implementations. |
| Hash Table + Preprocessed Suffix | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Find the Distinct Difference Array easy or hard?
Find the Distinct Difference Array is classified as an Easy problem on LeetCode with an acceptance rate above 70%. The challenge mainly involves correctly tracking distinct elements in prefixes and suffixes using sets or counting arrays.
Find the Distinct Difference Array Python/Java solution
Python solutions typically use the built-in set to track distinct elements while computing prefix and suffix counts. Java implementations commonly use HashSet or frequency arrays depending on constraints. Both implementations achieve O(n) time complexity.
How to solve Find the Distinct Difference Array in O(n)?
First compute suffix distinct counts by iterating from right to left and inserting values into a set. Then iterate from left to right with another set for the prefix. At each index compute prefixDistinct minus suffixDistinct[i+1]. Each operation is constant time, so the full algorithm runs in linear time.
What is the best approach for Find the Distinct Difference Array?
The best approach uses prefix and suffix tracking with hash sets. Precompute the number of distinct elements in each suffix, then iterate from left to right while maintaining a prefix set. For each index, subtract the suffix distinct count from the prefix distinct count. This runs in O(n) time and O(n) space.
Is Find the Distinct Difference Array asked at Google/Amazon/Meta?
Problems involving prefix counts, distinct tracking, and hash sets appear frequently in interviews at companies like Amazon and Google. While this exact problem may not appear verbatim, the pattern of maintaining prefix and suffix statistics across an array is commonly tested.
What data structure is used in Find the Distinct Difference Array?
The main data structure is a hash set or hash table to track unique elements in the prefix and suffix. Some optimized solutions replace the hash set with a frequency array when the value range is small, allowing constant-time updates and reduced overhead.
What is the time complexity of Find the Distinct Difference Array?
The optimal solution runs in O(n) time because the array is scanned only twice—once to compute suffix distinct counts and once to compute prefix differences. Each insertion or lookup in the hash set is O(1) on average. Space complexity is O(n) for storing suffix counts and tracking distinct elements.