Sum Squared Distinct Counts Across Large Subarray Inputs
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
# Sum Squared Distinct Counts Across Large Subarray Inputs
You are given a 0-indexed integer array `nums`. For a nonempty contiguous subarray `nums[i..j]`, where `0 <= i <= j < nums.length`, its distinct count is the number of different values appearing in that interval.
Return the sum of the squares of the distinct counts of all nonempty subarrays, modulo `10^9 + 7`. Subarrays at different index intervals contribute separately, even if they contain identical sequences of values.
### Examples
**Example 1**
```text
Input: nums = [3,5,3,5]
Output: 28
```
The four single-element intervals contribute `4`. All three length-two intervals contain two distinct values and contribute `12` in total. The two length-three intervals contribute `8`, and the whole array contributes `4`. The total is `4 + 12 + 8 + 4 = 28`.
**Example 2**
```text
Input: nums = [7,7,7]
Output: 6
```
There are six nonempty index intervals, and each contains only one distinct value. Their squared counts sum to `6`.
### Constraints
- `1 <= nums.length <= 10^5`.
- `1 <= nums[i] <= 10^5`.
### Clarifying Questions
- Is a subarray contiguous and nonempty? Yes; it is exactly one inclusive interval of indices.
- Do duplicate occurrences increase the distinct count? No; they contribute only one distinct value within that interval.
- Are matching sequences at different positions counted separately? Yes; intervals are identified by their endpoints.
- Is the square applied before or after summing distinct counts? Square each interval's count first, then sum those squares.
- Must the large exact total be returned? Return its remainder modulo `10^9 + 7` as specified.
### C++ Interface
```cpp
class Solution {
public:
int sumCounts(vector<int>& nums) {
}
};
```
### Reasoning Checkpoints
- Cover all index intervals while handling repeated values correctly.
- Explain how work is shared between successive endpoints at the maximum length.
- Derive the squared-count update and keep intermediate arithmetic safe.
```hint Track where a value last appeared
When appending a value at index r whose previous occurrence was p, which start positions gain one new distinct value? Use (d + 1)^2 - d^2 = 2d + 1, and maintain the needed interval sum with a range-update data structure.
```
Overview: Sum the squared distinct-value count over every nonempty contiguous subarray for up to 100000 elements, returning the result modulo the specified modulus.
