Skip to main content
Back to problems
#2670
Easy Algorithms

Find the distinct difference array

Array Hash Table
77.1% acceptance
Feb 25, 2026
369
38
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.

Solution

Rust
Time O(n)
Space O(n)
LeetCode
solution.rs 
impl Solution {
  pub fn distinct_difference_array(nums: Vec<i32>) -> Vec<i32> {
    use std::collections::HashSet;
    let n = nums.len();
    let mut result = vec![0i32; n];
    for i in 0..n {
      let prefix: HashSet<i32> = nums[0..=i].iter().cloned().collect();
      let suffix: HashSet<i32> = nums[i+1..].iter().cloned().collect();
      result[i] = prefix.len() as i32 - suffix.len() as i32;
    }
    result
  }
}