Problem Description

You are given a 0-indexed array nums of length n.

For each position i in the array, you need to calculate the distinct difference, which is:

• The number of distinct elements in the prefix nums[0, ..., i] (from start to position i, inclusive)
• Minus the number of distinct elements in the suffix nums[i + 1, ..., n - 1] (from position i + 1 to the end)

The result should be an array diff where diff[i] contains the distinct difference for position i.

For example, if at position i:

• The prefix nums[0, ..., i] has 5 distinct elements
• The suffix nums[i + 1, ..., n - 1] has 3 distinct elements
• Then diff[i] = 5 - 3 = 2

Special case: When i = n - 1 (last element), the suffix is empty, so it has 0 distinct elements.

The problem asks you to return the distinct difference array for the entire input array nums.

Intuition

The straightforward approach would be to calculate the distinct elements in the prefix and suffix for each position i separately. However, this would involve repeatedly counting distinct elements, leading to inefficiency.

The key insight is that we can precompute the distinct element counts for all suffixes first. Why suffixes? Because as we iterate through the array from left to right to build our answer, we're naturally building prefixes incrementally - we can maintain the prefix's distinct elements using a set that grows as we move forward.

Here's the thought process:

1. Precompute suffix information: If we traverse the array from right to left, we can calculate and store the number of distinct elements for each suffix nums[i, ..., n-1] in an array suf. We use a set to track distinct elements as we move leftward.

2. Calculate the answer while building prefixes: Now traverse the array from left to right. At each position i:

   • We add nums[i] to our set, which now contains all distinct elements in the prefix nums[0, ..., i]
   • The number of distinct elements in the prefix is simply the size of our set
   • The number of distinct elements in the suffix nums[i+1, ..., n-1] is already stored in suf[i+1]
   • The distinct difference is len(prefix_set) - suf[i+1]

This approach is efficient because we only traverse the array twice and use sets for O(1) average-case lookups and insertions. We avoid recalculating the same information multiple times by preprocessing the suffix counts.

Solution Approach

The solution uses a hash table (set) and preprocessed suffix array to efficiently calculate the distinct differences.

Step 1: Preprocess Suffix Array

First, we create a suffix array suf of size n + 1, where suf[i] stores the number of distinct elements in the suffix starting from index i.

suf = [0] * (n + 1)
s = set()
for i in range(n - 1, -1, -1):
    s.add(nums[i])
    suf[i] = len(s)

• We traverse the array from right to left (from index n-1 to 0)
• For each position i, we add nums[i] to the set s
• The size of the set gives us the number of distinct elements in nums[i, ..., n-1]
• We store this count in suf[i]
• Note: suf[n] = 0 by default, representing an empty suffix

Step 2: Calculate Distinct Differences

Next, we clear the set and traverse the array from left to right to build the answer:

s.clear()
ans = [0] * n
for i, x in enumerate(nums):
    s.add(x)
    ans[i] = len(s) - suf[i + 1]

• We reuse the same set s, but now to track distinct elements in the prefix
• For each position i:
  • Add nums[i] to the set (building the prefix nums[0, ..., i])
  • len(s) gives the number of distinct elements in the prefix
  • suf[i + 1] gives the number of distinct elements in the suffix nums[i + 1, ..., n - 1]
  • The distinct difference is len(s) - suf[i + 1]

Time Complexity: O(n) - We traverse the array twice, and set operations (add, len) are O(1) on average.

Space Complexity: O(n) - We use an additional array suf of size n + 1 and a set that can contain at most n elements.

Example Walkthrough

Let's walk through the solution with nums = [3, 2, 3, 4, 2].

Step 1: Build the suffix array from right to left

We create suf = [0, 0, 0, 0, 0, 0] and an empty set s.

• i = 4: Add nums[4] = 2 to set → s = {2} → suf[4] = 1
• i = 3: Add nums[3] = 4 to set → s = {2, 4} → suf[3] = 2
• i = 2: Add nums[2] = 3 to set → s = {2, 3, 4} → suf[2] = 3
• i = 1: Add nums[1] = 2 to set → s = {2, 3, 4} (2 already exists) → suf[1] = 3
• i = 0: Add nums[0] = 3 to set → s = {2, 3, 4} (3 already exists) → suf[0] = 3

Result: suf = [3, 3, 3, 2, 1, 0]

This means:

• suf[0] = 3: suffix starting at index 0 has 3 distinct elements
• suf[1] = 3: suffix starting at index 1 has 3 distinct elements
• suf[2] = 3: suffix starting at index 2 has 3 distinct elements
• suf[3] = 2: suffix starting at index 3 has 2 distinct elements
• suf[4] = 1: suffix starting at index 4 has 1 distinct element
• suf[5] = 0: empty suffix has 0 distinct elements

Step 2: Calculate distinct differences from left to right

Clear the set and create ans = [0, 0, 0, 0, 0].

• i = 0: Add nums[0] = 3 to set → s = {3} → prefix has 1 distinct, suffix suf[1] = 3 → ans[0] = 1 - 3 = -2
• i = 1: Add nums[1] = 2 to set → s = {2, 3} → prefix has 2 distinct, suffix suf[2] = 3 → ans[1] = 2 - 3 = -1
• i = 2: Add nums[2] = 3 to set → s = {2, 3} (3 already exists) → prefix has 2 distinct, suffix suf[3] = 2 → ans[2] = 2 - 2 = 0
• i = 3: Add nums[3] = 4 to set → s = {2, 3, 4} → prefix has 3 distinct, suffix suf[4] = 1 → ans[3] = 3 - 1 = 2
• i = 4: Add nums[4] = 2 to set → s = {2, 3, 4} (2 already exists) → prefix has 3 distinct, suffix suf[5] = 0 → ans[4] = 3 - 0 = 3

Final answer: [-2, -1, 0, 2, 3]

This matches our expected result where:

• At index 0: prefix [3] has 1 distinct, suffix [2,3,4,2] has 3 distinct → 1 - 3 = -2
• At index 1: prefix [3,2] has 2 distinct, suffix [3,4,2] has 3 distinct → 2 - 3 = -1
• At index 2: prefix [3,2,3] has 2 distinct, suffix [4,2] has 2 distinct → 2 - 2 = 0
• At index 3: prefix [3,2,3,4] has 3 distinct, suffix [2] has 1 distinct → 3 - 1 = 2
• At index 4: prefix [3,2,3,4,2] has 3 distinct, suffix [] has 0 distinct → 3 - 0 = 3

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. The algorithm consists of two sequential passes through the array:

• The first loop iterates from index n-1 to 0, performing constant-time operations (set addition and length calculation) at each step, taking O(n) time.
• The second loop iterates through all elements using enumerate, performing constant-time operations (set addition, length calculation, and subtraction) at each step, also taking O(n) time.
• Since these loops run sequentially, the total time complexity is O(n) + O(n) = O(n).

The space complexity is O(n), where n is the length of the array nums. The space usage includes:

• The suf array of size n + 1, which requires O(n) space.
• The ans array of size n, which requires O(n) space.
• The set s which can contain at most n distinct elements from nums, requiring O(n) space in the worst case.
• The total space complexity is O(n) + O(n) + O(n) = O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error in Suffix Array Indexing

The Pitfall: A common mistake is incorrectly indexing the suffix array when calculating the distinct difference. Developers often confuse whether suf[i] should represent:

• The suffix starting from index i (including nums[i]), or
• The suffix starting from index i + 1 (excluding nums[i])

This confusion leads to using suf[i] instead of suf[i + 1] when calculating the answer, resulting in incorrect results.

Example of Incorrect Code:

# WRONG: Using suf[i] instead of suf[i + 1]
for i, x in enumerate(nums):
    s.add(x)
    ans[i] = len(s) - suf[i]  # ❌ This includes nums[i] in both prefix and suffix

Why This Happens: The problem requires the suffix to start from i + 1 (not including the current element), but when building the suffix array, suf[i] naturally stores the count starting from index i. This creates a mismatch between the stored values and what we need.

The Solution: Always use suf[i + 1] when calculating the distinct difference at position i:

for i, x in enumerate(nums):
    s.add(x)
    ans[i] = len(s) - suf[i + 1]  # ✅ Correct: suffix starts from i + 1

2. Not Clearing the Set Between Prefix and Suffix Calculations

The Pitfall: Forgetting to clear the set after building the suffix array and before calculating the prefix leads to incorrect prefix counts.

Example of Incorrect Code:

# Build suffix array
s = set()
for i in range(n - 1, -1, -1):
    s.add(nums[i])
    suf[i] = len(s)

# WRONG: Forgot to clear the set
# s.clear()  # ❌ Missing this line

ans = [0] * n
for i, x in enumerate(nums):
    s.add(x)  # Set already contains all elements from suffix calculation
    ans[i] = len(s) - suf[i + 1]

The Solution: Always clear the set between the two phases:

s.clear()  # ✅ Essential: Reset the set before prefix calculation

3. Incorrect Suffix Array Size

The Pitfall: Creating the suffix array with size n instead of n + 1, which causes an index out of bounds error when accessing suf[n] (needed when i = n - 1).

Example of Incorrect Code:

suf = [0] * n  # ❌ Should be n + 1
# Later when i = n - 1:
ans[n-1] = len(s) - suf[n]  # IndexError: list index out of range

The Solution: Always allocate n + 1 elements for the suffix array:

suf = [0] * (n + 1)  # ✅ Correct size to handle suf[n] = 0

The extra element suf[n] represents an empty suffix with 0 distinct elements.