Find the Distinct Difference Array — Easy Problem & Solution

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 <= 50
• 1 <= nums[i] <= 50

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

1. Sweep i from n - 1 down to 0, inserting nums[i] into a set after recording sufCount[i] — the size of the set covering nums[i+1..].
2. Sweep i from 0 upward, inserting nums[i] into a second set first, so its size is the prefix distinct count for nums[0..i].
3. 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] includes nums[i] itself, which the definition excludes.
• The last suffix is empty and must contribute 0, not 1.

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 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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Special Array I Easy
• Type of Triangle Easy
• Find the Losers of the Circular Game Easy
• Form Smallest Number From Two Digit Arrays Easy
• Delete Greatest Value in Each Row Easy
• The Employee That Worked on the Longest Task Easy