Algorithms
Hard
2916
3139
Subarrays Distinct Element Sum of Squares II
subarrays-distinct-element-sum-of-squares-ii
"""
You are given a 0-indexed integer array nums.

The distinct count of a subarray of nums is defined as:

 * Let nums[i..j] be a subarray of nums consisting of all the indices from i to j such that 0 <= i <= j < nums.length. Then the number of distinct values in nums[i..j] is called the distinct count of nums[i..j].

Return the sum of the squares of distinct counts of all subarrays of nums.

Since the answer may be very large, return it modulo 109 + 7.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,2,1]
Output: 15
Explanation: 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
Explanation: 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
"""
class Solution:
    def sumCounts(self, nums: List[int]) -> int:
        
You are given a 0-indexed integer array nums.

The distinct count of a subarray of nums is defined as:

 * Let nums[i..j] be a subarray of nums consisting of all the indices from i to j such that 0 <= i <= j < nums.length. Then the number of distinct values in nums[i..j] is called the distinct count of nums[i..j].

Return the sum of the squares of distinct counts of all subarrays of nums.

Since the answer may be very large, return it modulo 109 + 7.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,2,1]
Output: 15
Explanation: 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
Explanation: 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


Please complete the code below to solve above prblem:
```python
class Solution:
    def sumCounts(self, nums: List[int]) -> int:
        
```

my_solution = Solution()

test_input = { "nums": [1,2,1] }
assert my_solution.sumCounts(**test_input) == 15

test_input = { "nums": [2,2] }
assert my_solution.sumCounts(**test_input) == 3

test_input = { "nums": [2,2,5,5] }
assert my_solution.sumCounts(**test_input) == 22

test_input = { "nums": [5,2,4,2,1,3,2,4,3,1] }
assert my_solution.sumCounts(**test_input) == 578

test_input = { "nums": [2,3,2,1,2,5,3,4,5,2] }
assert my_solution.sumCounts(**test_input) == 629

test_input = { "nums": [5,1,5,2,3,5,1,5,1] }
assert my_solution.sumCounts(**test_input) == 385

test_input = { "nums": [4,5,4,3,4,2] }
assert my_solution.sumCounts(**test_input) == 120

test_input = { "nums": [2] }
assert my_solution.sumCounts(**test_input) == 1

test_input = { "nums": [3,4,2,5,2,4,1,2,2,5] }
assert my_solution.sumCounts(**test_input) == 535

test_input = { "nums": [4,4,2,4,1] }
assert my_solution.sumCounts(**test_input) == 57

test_input = { "nums": [2,2,5] }
assert my_solution.sumCounts(**test_input) == 12

test_input = { "nums": [4,5,1,2,2,1,3,3] }
assert my_solution.sumCounts(**test_input) == 266

test_input = { "nums": [3,1,5,5,2,3,2,2,1] }
assert my_solution.sumCounts(**test_input) == 334

test_input = { "nums": [2,5,2,5,3,2,5,2] }
assert my_solution.sumCounts(**test_input) == 205

test_input = { "nums": [5,4,1,4,5,2,4] }
assert my_solution.sumCounts(**test_input) == 203

test_input = { "nums": [1,3,3,4,3,1,2,1] }
assert my_solution.sumCounts(**test_input) == 253

test_input = { "nums": [4] }
assert my_solution.sumCounts(**test_input) == 1

test_input = { "nums": [1,4,2,1,5,4,3,1,4] }
assert my_solution.sumCounts(**test_input) == 507

test_input = { "nums": [2,4,5,3,2,5,1,5,4,4] }
assert my_solution.sumCounts(**test_input) == 626

test_input = { "nums": [3,4,1,4,5,2,2] }
assert my_solution.sumCounts(**test_input) == 220

test_input = { "nums": [3,5,1,1,3] }
assert my_solution.sumCounts(**test_input) == 62

test_input = { "nums": [4,3,2,5,3] }
assert my_solution.sumCounts(**test_input) == 89

test_input = { "nums": [2,5] }
assert my_solution.sumCounts(**test_input) == 6

test_input = { "nums": [1,5,1,4,5] }
assert my_solution.sumCounts(**test_input) == 70

test_input = { "nums": [5,1] }
assert my_solution.sumCounts(**test_input) == 6

test_input = { "nums": [4,5,4,3,3,5,3] }
assert my_solution.sumCounts(**test_input) == 138

test_input = { "nums": [5,4,3] }
assert my_solution.sumCounts(**test_input) == 20

test_input = { "nums": [5,5,3,3,4,5,4,5,5] }
assert my_solution.sumCounts(**test_input) == 234

test_input = { "nums": [3,1,5,5,3,4,5,5,1,4] }
assert my_solution.sumCounts(**test_input) == 456

test_input = { "nums": [4,2,3,1,1] }
assert my_solution.sumCounts(**test_input) == 81

test_input = { "nums": [4,5,3,1,2,5,5,3,5] }
assert my_solution.sumCounts(**test_input) == 434

test_input = { "nums": [3,2,1,2,5,2,4,5,1,5] }
assert my_solution.sumCounts(**test_input) == 531

test_input = { "nums": [1,3,1,4,4] }
assert my_solution.sumCounts(**test_input) == 62

test_input = { "nums": [5,1,2,1,2,1,2,3,1] }
assert my_solution.sumCounts(**test_input) == 257

test_input = { "nums": [2,4] }
assert my_solution.sumCounts(**test_input) == 6

test_input = { "nums": [4,5,4,5] }
assert my_solution.sumCounts(**test_input) == 28

test_input = { "nums": [3,1,5,5,5,4,3,3,2] }
assert my_solution.sumCounts(**test_input) == 334

test_input = { "nums": [3,2,5,2,1,5,3] }
assert my_solution.sumCounts(**test_input) == 203

test_input = { "nums": [4,4,2,5,5,4,2,2,1] }
assert my_solution.sumCounts(**test_input) == 294

test_input = { "nums": [1] }
assert my_solution.sumCounts(**test_input) == 1

test_input = { "nums": [1,1,3,3,3,4,4] }
assert my_solution.sumCounts(**test_input) == 96

test_input = { "nums": [3,2,2,3,4] }
assert my_solution.sumCounts(**test_input) == 57

test_input = { "nums": [1,5,3,2,4,4] }
assert my_solution.sumCounts(**test_input) == 161

test_input = { "nums": [5,4,1,1,3] }
assert my_solution.sumCounts(**test_input) == 69

test_input = { "nums": [4,3,3,5,3,4,5,3,3,1] }
assert my_solution.sumCounts(**test_input) == 376

test_input = { "nums": [2,3,4,1,5,1,3,3,4] }
assert my_solution.sumCounts(**test_input) == 432

test_input = { "nums": [5,1,4,2,1,1] }
assert my_solution.sumCounts(**test_input) == 129

test_input = { "nums": [5,4,4,1] }
assert my_solution.sumCounts(**test_input) == 30

test_input = { "nums": [1,5,1,3,2,1] }
assert my_solution.sumCounts(**test_input) == 139

test_input = { "nums": [5,3] }
assert my_solution.sumCounts(**test_input) == 6

test_input = { "nums": [4,1,4,3] }
assert my_solution.sumCounts(**test_input) == 38

test_input = { "nums": [1,5,4,3,4,2,4,5,5,4] }
assert my_solution.sumCounts(**test_input) == 513

test_input = { "nums": [4,2,3,4,3,2,5,4,4] }
assert my_solution.sumCounts(**test_input) == 378

test_input = { "nums": [2,3,3,2,1,5,2,2] }
assert my_solution.sumCounts(**test_input) == 262

test_input = { "nums": [2,1,4,2,4,1,4,3] }
assert my_solution.sumCounts(**test_input) == 243

test_input = { "nums": [1,4,4,1,3] }
assert my_solution.sumCounts(**test_input) == 57

test_input = { "nums": [2,3,2,1] }
assert my_solution.sumCounts(**test_input) == 38

test_input = { "nums": [1,4,2,1] }
assert my_solution.sumCounts(**test_input) == 43

test_input = { "nums": [2,4,3,2,5,1] }
assert my_solution.sumCounts(**test_input) == 169

test_input = { "nums": [2,5,3,2,1,3,1,3,2] }
assert my_solution.sumCounts(**test_input) == 348

test_input = { "nums": [4,1] }
assert my_solution.sumCounts(**test_input) == 6

test_input = { "nums": [4,3,1,4,3,4,3,4,1] }
assert my_solution.sumCounts(**test_input) == 263

test_input = { "nums": [5,1,1,1,4,3] }
assert my_solution.sumCounts(**test_input) == 89

test_input = { "nums": [4,5] }
assert my_solution.sumCounts(**test_input) == 6

test_input = { "nums": [5,2,2,3,1,2,5,3] }
assert my_solution.sumCounts(**test_input) == 289

test_input = { "nums": [3,2,4] }
assert my_solution.sumCounts(**test_input) == 20

test_input = { "nums": [5,3,5,2,3,2] }
assert my_solution.sumCounts(**test_input) == 106

test_input = { "nums": [3,2,1] }
assert my_solution.sumCounts(**test_input) == 20

test_input = { "nums": [4,4,2,4,3] }
assert my_solution.sumCounts(**test_input) == 57

test_input = { "nums": [1,4,4] }
assert my_solution.sumCounts(**test_input) == 12

test_input = { "nums": [1,4,4,3,1,2,1,4,3] }
assert my_solution.sumCounts(**test_input) == 387

test_input = { "nums": [1,5,4,2,5,5,5,3] }
assert my_solution.sumCounts(**test_input) == 249

test_input = { "nums": [2,1,5,3] }
assert my_solution.sumCounts(**test_input) == 50

test_input = { "nums": [2,3,5,1,5,2,3,2,3,4] }
assert my_solution.sumCounts(**test_input) == 533

test_input = { "nums": [5,3,4,4,3,5,4,5] }
assert my_solution.sumCounts(**test_input) == 202

test_input = { "nums": [4,4,2,2,4,1] }
assert my_solution.sumCounts(**test_input) == 80

test_input = { "nums": [2,3] }
assert my_solution.sumCounts(**test_input) == 6

test_input = { "nums": [4,2,3,2] }
assert my_solution.sumCounts(**test_input) == 38

test_input = { "nums": [1,2,2] }
assert my_solution.sumCounts(**test_input) == 12

test_input = { "nums": [4,1,5,1,5,4,5,1] }
assert my_solution.sumCounts(**test_input) == 205

test_input = { "nums": [4,5,3,1] }
assert my_solution.sumCounts(**test_input) == 50

test_input = { "nums": [4,2,3,4,2,4,3,3,2] }
assert my_solution.sumCounts(**test_input) == 275

test_input = { "nums": [4,3] }
assert my_solution.sumCounts(**test_input) == 6

test_input = { "nums": [1,3,5,4,4,4] }
assert my_solution.sumCounts(**test_input) == 113

test_input = { "nums": [1,2,4,2,1,2,2,4,1,3] }
assert my_solution.sumCounts(**test_input) == 391

test_input = { "nums": [4,2,5,3,2] }
assert my_solution.sumCounts(**test_input) == 89

test_input = { "nums": [3,4,5,3,2,5] }
assert my_solution.sumCounts(**test_input) == 144

test_input = { "nums": [5,4,5] }
assert my_solution.sumCounts(**test_input) == 15

test_input = { "nums": [2,4,5,1] }
assert my_solution.sumCounts(**test_input) == 50

test_input = { "nums": [5,4,1,4,2,1,5] }
assert my_solution.sumCounts(**test_input) == 203

test_input = { "nums": [2,3,3,2,2,3,1] }
assert my_solution.sumCounts(**test_input) == 110

test_input = { "nums": [1,4,2,5] }
assert my_solution.sumCounts(**test_input) == 50

test_input = { "nums": [3] }
assert my_solution.sumCounts(**test_input) == 1

test_input = { "nums": [5] }
assert my_solution.sumCounts(**test_input) == 1

test_input = { "nums": [1,3,5,3,2,1,1,4,3] }
assert my_solution.sumCounts(**test_input) == 441

test_input = { "nums": [1,5,2,2,3,3,3] }
assert my_solution.sumCounts(**test_input) == 140

test_input = { "nums": [1,2,1,4,5,5,4,1,1,1] }
assert my_solution.sumCounts(**test_input) == 407

test_input = { "nums": [2,2,1,1,1,2,5,4,5] }
assert my_solution.sumCounts(**test_input) == 296

test_input = { "nums": [3,2,3] }
assert my_solution.sumCounts(**test_input) == 15

test_input = { "nums": [2,1,5,4,3,3,2,1,5,5] }
assert my_solution.sumCounts(**test_input) == 652