Find the Distinct Difference Array

Easy
603.

Find the Distinct Difference Array

Find the Distinct Difference Array is an easy coding problem on arrays, hash table and prefix sum, asked in Amazon and Wipro interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var distinctDifferenceArray = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

Hints for Find the Distinct Difference Array

  1. Hint 1

    Two quantities per index: distinct in the prefix, distinct in the suffix.

  2. Hint 2

    One right-to-left pass can precompute every suffix count into an array.

  3. 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

  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

Java

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