Sum Squared Distinct Counts Across All Subarrays
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Other
# Sum Squared Distinct Counts Across All Subarrays
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 that appear in that interval.
Return the sum of the squares of the distinct counts of all nonempty subarrays. Subarrays at different index intervals count separately, even if their values are identical.
### Examples
**Example 1**
```text
Input: nums = [2,3,4]
Output: 20
```
The three single-element subarrays contribute `3 * 1^2 = 3`. The two length-two subarrays each have two distinct values and contribute `2 * 2^2 = 8`. The whole array has three distinct values and contributes `3^2 = 9`. The total is `3 + 8 + 9 = 20`.
**Example 2**
```text
Input: nums = [4,4,5]
Output: 12
```
The three single-element intervals contribute `3`. The length-two intervals `[4,4]` and `[4,5]` contribute `1` and `4`. The whole array `[4,4,5]` contributes `4`, for a total of `3 + 1 + 4 + 4 = 12`.
### Constraints
- `1 <= nums.length <= 100`.
- `1 <= nums[i] <= 100`.
### Clarifying Questions
- Are subarrays contiguous? Yes; each is an inclusive interval of indices.
- Is an empty subarray included? No.
- Does repeating a value increase its distinct count? No; each different value is counted once within that interval.
- Should identical value sequences at different positions be merged? No; every index interval contributes separately.
- Is the answer reduced modulo a number? No; return the exact integer sum for these bounds.
### C++ Interface
```cpp
class Solution {
public:
int sumCounts(vector<int>& nums) {
}
};
```
### Reasoning Checkpoints
- Count each nonempty index interval exactly once.
- Distinguish the number of values present from the number of element occurrences.
- Square each interval's count before adding it, and justify the numeric range.
```hint Extend one interval at a time
Fix a left endpoint and extend the right endpoint. With values bounded by 100, a small presence table can tell whether the new element changes the distinct count.
```
Overview: For every nonempty contiguous subarray, square its number of distinct values and return the exact sum under the stated small input bounds.