Skip to main content
Talentd

Find the Distinct Difference Array - Solution & Explanation

EasyArrayHash Table15 min readAsked at: Amazon
Practice this problem

Problem Statement

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

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.

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.

Code

PythonJavaC#

Python

Java

C#

Complexity

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.

Try this approach in the editor →

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.

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.

Code

CJavaScript

C

JavaScript

Complexity

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.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Prefix and Suffix Sets with IterationO(n)O(n)General case. Clear logic using hash sets to track unique elements.
Optimized Prefix and Suffix Tracking with ArraysO(n + k)O(k)Best when value range is small and predictable. Avoids hash table overhead.

Video Solution

Find the Distinct Difference Array | Leetcode 2670 | Weekly Contest 344 • Technosage • 2,703 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Find the Distinct Difference Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Left and Right Sum Differences