LeetCode 2670 - Find the Distinct Difference Array

The problem asks us to compute the distinct difference array for a given integer array nums. For each index i in the array, we calculate the difference between the number of distinct elements in the prefix nums[0, ...

leetcodeeasyarrayhash-table

LeetCode Problem 2670

Difficulty: 🟢 Easy
Topics: Array, Hash Table

Solution

Problem Understanding

The problem asks us to compute the distinct difference array for a given integer array nums. For each index i in the array, we calculate the difference between the number of distinct elements in the prefix nums[0, ..., i] and the number of distinct elements in the suffix nums[i + 1, ..., n - 1]. The result is stored in a new array diff of the same length as nums.

For example, if the array is [3,2,3,4,2], at index 0, the prefix is [3] (1 distinct element) and the suffix is [2,3,4,2] (3 distinct elements), so diff[0] = 1 - 3 = -2. We repeat this calculation for each index.

The input array has a length between 1 and 50, and each element is between 1 and 50. This small constraint allows us to use extra space or slightly less efficient algorithms without worrying about performance degradation. Important edge cases include arrays with all identical elements, arrays with all unique elements, and the minimal array size of 1. The problem guarantees at least one element, so we do not need to handle empty arrays.

Approaches

The brute-force approach is straightforward: for each index i, compute the number of distinct elements in the prefix and suffix separately. We can use sets to keep track of distinct elements. Although this approach is correct, it repeatedly recomputes distinct elements for overlapping subarrays, which is inefficient.

The key observation for an optimal solution is that we can incrementally build the distinct element count for the prefix and suffix using a set while iterating through the array. First, we compute the suffix distinct counts for all indices by iterating from the end to the start. Then, we iterate from the start to compute prefix distinct counts while simultaneously computing the difference. This avoids recomputing the distinct count multiple times and reduces unnecessary operations.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(n) Recompute distinct elements for each prefix and suffix using sets
Optimal O(n) O(n) Use sets to incrementally track prefix and suffix distinct counts

Algorithm Walkthrough

  1. Initialize an array suffixDistinct of length n to store the number of distinct elements in the suffix starting at each index.
  2. Initialize an empty set seen to track elements while computing suffixDistinct.
  3. Iterate backward through nums from the last index to the first. At each index i, add nums[i] to seen and set suffixDistinct[i] = len(seen). This captures the number of distinct elements in the suffix starting from i.
  4. Initialize an empty set prefixSeen to track elements in the prefix.
  5. Initialize the result array diff of length n.
  6. Iterate forward through nums from index 0 to n - 1. At each index i, add nums[i] to prefixSeen, then compute diff[i] = len(prefixSeen) - (suffixDistinct[i+1] if i < n - 1 else 0). This ensures the suffix count uses 0 for the last element.
  7. Return the diff array.

Why it works: By precomputing the distinct counts in the suffix and incrementally building the prefix distinct count, we ensure that each diff[i] is computed correctly without redundant calculations. This guarantees correctness and runs efficiently in linear time.

Python Solution

from typing import List

class Solution:
    def distinctDifferenceArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        suffixDistinct = [0] * n
        seen = set()
        
        # Compute suffix distinct counts
        for i in range(n - 1, -1, -1):
            seen.add(nums[i])
            suffixDistinct[i] = len(seen)
        
        prefixSeen = set()
        diff = [0] * n
        
        # Compute prefix distinct counts and differences
        for i in range(n):
            prefixSeen.add(nums[i])
            suffixCount = suffixDistinct[i + 1] if i < n - 1 else 0
            diff[i] = len(prefixSeen) - suffixCount
        
        return diff

The Python implementation uses two passes through the array: a backward pass to build suffixDistinct and a forward pass to compute the differences while maintaining the prefix set. Using sets ensures that distinct elements are tracked correctly. The conditional if i < n - 1 else 0 handles the edge case for the last element where the suffix is empty.

Go Solution

func distinctDifferenceArray(nums []int) []int {
    n := len(nums)
    suffixDistinct := make([]int, n)
    seen := make(map[int]struct{})

    // Compute suffix distinct counts
    for i := n - 1; i >= 0; i-- {
        seen[nums[i]] = struct{}{}
        suffixDistinct[i] = len(seen)
    }

    prefixSeen := make(map[int]struct{})
    diff := make([]int, n)

    // Compute prefix distinct counts and differences
    for i := 0; i < n; i++ {
        prefixSeen[nums[i]] = struct{}{}
        suffixCount := 0
        if i < n-1 {
            suffixCount = suffixDistinct[i+1]
        }
        diff[i] = len(prefixSeen) - suffixCount
    }

    return diff
}

In Go, sets are implemented using a map[int]struct{}. The logic mirrors the Python solution, using two passes and maps to track distinct elements. We handle the suffix edge case explicitly by checking if i < n-1.

Worked Examples

Example: nums = [3,2,3,4,2]

i prefixSeen suffixDistinct[i+1] diff[i]
0 {3} 3 1 - 3 = -2
1 {2,3} 3 2 - 3 = -1
2 {2,3} 2 2 - 2 = 0
3 {2,3,4} 1 3 - 1 = 2
4 {2,3,4} 0 3 - 0 = 3

The resulting array is [-2, -1, 0, 2, 3].

Complexity Analysis

Measure Complexity Explanation
Time O(n) Two passes through the array: backward for suffix, forward for prefix and diff calculation
Space O(n) Stores suffix counts and sets for prefix and suffix tracking

Given n <= 50, this solution is extremely efficient and easily handles all valid inputs.

Test Cases

# Provided examples
assert Solution().distinctDifferenceArray([1,2,3,4,5]) == [-3,-1,1,3,5]  # strictly increasing
assert Solution().distinctDifferenceArray([3,2,3,4,2]) == [-2,-1,0,2,3]  # duplicates

# Edge cases
assert Solution().distinctDifferenceArray([1]) == [1]  # single element
assert Solution().distinctDifferenceArray([1,1,1,1]) == [0,0,0,1]  # all identical
assert Solution().distinctDifferenceArray([1,2,1,2,1,2]) == [-1,0,0,0,0,1]  # alternating duplicates
assert Solution().distinctDifferenceArray([5,4,3,2,1]) == [1,-1,-1,-1,5]  # strictly decreasing
Test Why
[1,2,3,4,5] Tests strictly increasing sequence with all unique elements
[3,2,3,4,2] Tests array with duplicates
[1] Tests minimal input size
[1,1,1,1] Tests array with all identical elements
[1,2,1,2,1,2] Tests alternating duplicates
[5,4,3,2,1] Tests strictly decreasing sequence

Edge Cases

One important edge case is a single-element array. Here, the prefix contains the element and the suffix is empty, so the difference is always the length of the prefix minus zero. The implementation handles this by checking the suffix index and defaulting to 0 when i is the last index.

Another edge case is an array with all identical elements. Each prefix and suffix will only ever count one distinct element, except the last element, where the suffix is empty. The code correctly calculates the differences by using the length of the sets.

A third edge case is alternating duplicates. For example, [1,2,1,2] tests that the implementation correctly tracks distinct counts in both prefix and suffix when elements repeat non-consecutively. Using sets for prefix and suffix ensures duplicates do not inflate the count.

These edge cases