Scale Engineer

Find the Distinct Difference Array

Easy
#2422Time: O(n^2). The outer loop runs `n` times. For each `i`, the inner loops for the prefix and suffix together iterate through `(i+1) + (n-1-i) = n` elements. Thus, the total time complexity is `n * n = O(n^2)`.Space: O(n). In each iteration of the outer loop, we create two `HashSet`s. The maximum combined size of these sets can be up to `n`. The result array `diff` also requires `O(n)` space.
Data structures
ArrayHash Table

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly translates the problem definition into code. For each index i, it iterates through the prefix nums[0...i] and the suffix nums[i+1...n-1] to count the distinct elements in each part using HashSets. The difference between these two counts gives the result for diff[i].

Algorithm

  • Initialize an integer array diff of size n.
  • For i from 0 to n-1:
    • Create a HashSet<Integer> prefixSet.
    • For j from 0 to i:
      • Add nums[j] to prefixSet.
    • Create a HashSet<Integer> suffixSet.
    • For k from i+1 to n-1:
      • Add nums[k] to suffixSet.
    • diff[i] = prefixSet.size() - suffixSet.size().
  • Return diff.

Walkthrough

The brute-force method is the most straightforward way to solve the problem. We iterate through each index i of the input array nums. For each i, we need to find the number of distinct elements in the prefix subarray nums[0...i] and the suffix subarray nums[i+1...n-1]. We can use a HashSet data structure to efficiently count distinct elements. We create one set for the prefix and another for the suffix. We populate them by iterating through the respective subarray parts and then find the difference of their sizes. This process is repeated for all indices from 0 to n-1.

import java.util.HashSet;import java.util.Set; class Solution {    public int[] distinctDifferenceArray(int[] nums) {        int n = nums.length;        int[] diff = new int[n];         for (int i = 0; i < n; i++) {            // Calculate distinct elements in the prefix nums[0...i]            Set<Integer> prefixDistinct = new HashSet<>();            for (int j = 0; j <= i; j++) {                prefixDistinct.add(nums[j]);            }             // Calculate distinct elements in the suffix nums[i+1...n-1]            Set<Integer> suffixDistinct = new HashSet<>();            for (int j = i + 1; j < n; j++) {                suffixDistinct.add(nums[j]);            }             diff[i] = prefixDistinct.size() - suffixDistinct.size();        }        return diff;    }}

Complexity

Time

O(n^2). The outer loop runs `n` times. For each `i`, the inner loops for the prefix and suffix together iterate through `(i+1) + (n-1-i) = n` elements. Thus, the total time complexity is `n * n = O(n^2)`.

Space

O(n). In each iteration of the outer loop, we create two `HashSet`s. The maximum combined size of these sets can be up to `n`. The result array `diff` also requires `O(n)` space.

Trade-offs

Pros

  • Simple to understand and implement.

  • Directly follows the problem statement, making the logic easy to verify.

Cons

  • Inefficient due to repeated calculations for prefixes and suffixes.

  • Its O(n^2) time complexity makes it unsuitable for large input sizes, although it passes for the given constraints.

Solutions

class Solution {public  int[] distinctDifferenceArray(int[] nums) {    int n = nums.length;    int[] suf = new int[n + 1];    Set<Integer> s = new HashSet<>();    for (int i = n - 1; i >= 0; --i) {      s.add(nums[i]);      suf[i] = s.size();    }    s.clear();    int[] ans = new int[n];    for (int i = 0; i < n; ++i) {      s.add(nums[i]);      ans[i] = s.size() - suf[i + 1];    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem