Subarrays Distinct Element Sum of Squares II

Start by tracking distinct counts for subarrays ending at each index using dynamic programming. Maintain a mapping to the last occurrence of elements and use prefix sums or Binary Indexed Tree to quickly compute contributions. This approach handles overlapping subarrays efficiently and scales to large arrays within constraints, avoiding naive enumeration that fails on performance.

Problem Statement

Given a 0-indexed integer array nums, compute the sum of the squares of distinct element counts for every possible contiguous subarray. Each subarray's distinct count is the number of unique integers it contains, and the sum should include all subarrays of nums.

Return an integer representing this sum. For example, if nums = [1,2,1], six subarrays exist, and their distinct counts squared sum to 15. Constraints: 1 <= nums.length <= 105, 1 <= nums[i] <= 105.

Examples

Example 1

Input: nums = [1,2,1]

Output: 15

Six possible subarrays are: [1]: 1 distinct value [2]: 1 distinct value [1]: 1 distinct value [1,2]: 2 distinct values [2,1]: 2 distinct values [1,2,1]: 2 distinct values The sum of the squares of the distinct counts in all subarrays is equal to 12 + 12 + 12 + 22 + 22 + 22 = 15.

Example 2

Input: nums = [2,2]

Output: 3

Three possible subarrays are: [2]: 1 distinct value [2]: 1 distinct value [2,2]: 1 distinct value The sum of the squares of the distinct counts in all subarrays is equal to 12 + 12 + 12 = 3.

Constraints

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105

Solution Approach

State Transition Dynamic Programming

Define dp[i] as the sum of squares of distinct counts for subarrays ending at index i. Use a map to track the last occurrence of each element. For each index, compute new contributions based on whether the element is new or repeating, updating dp[i] efficiently using previous results.

Binary Indexed Tree for Prefix Sums

Use a Binary Indexed Tree to maintain running sums of distinct counts. When adding a new element, update the tree at its last index and compute sum contributions in logarithmic time. This prevents recomputation of overlapping subarrays and accelerates large input handling.

Segment Tree Optimization

Alternatively, a Segment Tree can track ranges of distinct counts and allow range sum queries. Each update adjusts for the last occurrence of an element, and queries return sums of squares efficiently. This is especially useful for very large arrays where DP alone may be too slow.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on using DP with either BIT or Segment Tree, generally O(n log n) due to logarithmic updates and queries per index. Space complexity is O(n) for storing last occurrences and tree structures.

What Interviewers Usually Probe

• Check if candidate recognizes the state transition for subarrays ending at each index.
• Look for efficient use of BIT or Segment Tree instead of naive O(n^2) iteration.
• Candidate should track last occurrence to handle repeated elements correctly.

Common Pitfalls or Variants

Common pitfalls

• Naively enumerating all subarrays leads to timeouts for large n.
• Forgetting to update contributions when an element repeats in a subarray.
• Confusing sum of distinct counts with sum of distinct elements themselves.

Follow-up variants

• Compute sum of cubes instead of squares of distinct counts.
• Only consider subarrays of length exactly k.
• Handle multisets where duplicates increase the count differently.

FAQ

What is the best approach for Subarrays Distinct Element Sum of Squares II?

Use state transition dynamic programming combined with a BIT or Segment Tree to track distinct counts efficiently.

Can this problem be solved with a brute-force method?

Brute-force enumeration works only for very small arrays, but it fails for n up to 10^5 due to O(n^3) time complexity.

How do I handle repeated elements in subarrays?

Maintain the last occurrence index for each element and update the contribution to avoid counting duplicates multiple times.

Is a Segment Tree necessary for all inputs?

Not always; for moderate-sized arrays, DP with a Binary Indexed Tree is sufficient, but Segment Tree helps for large ranges and frequent updates.

What pattern does this problem mainly test?

It tests state transition dynamic programming focused on subarray sums with distinct element tracking.