Description
Subarrays Distinct Element Sum of Squares I
EasyYou 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 ofnumsconsisting of all the indices fromitojsuch that0 <= i <= j < nums.length. Then the number of distinct values innums[i..j]is called the distinct count ofnums[i..j].
Return the sum of the squares of distinct counts of all subarrays of nums.
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 = [1,1] Output: 3 Explanation: Three possible subarrays are: [1]: 1 distinct value [1]: 1 distinct value [1,1]: 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 <= 1001 <= nums[i] <= 100
Solutions
This function computes the sum of the squares of distinct counts over every contiguous subarray of nums. The outer loop fixes a starting index i, and for each start it creates a fresh Set to track which values have been seen so far. The inner loop extends the subarray one element at a time by moving j from i to the end, adding nums[j] to the set; because a Set ignores duplicates, set.size at any moment is exactly the number of distinct values in the subarray nums[i..j]. After each extension, the code adds set.size ** 2 (the distinct count squared) to the running total res. By the time both loops finish, every possible subarray has been visited once, so res holds the required answer. The approach runs in O(n²) time with O(n) extra space for the set.
/**
* @param {number[]} nums
* @return {number}
*/
var sumCounts = function(nums) {
let res = 0;
for (let i = 0; i < nums.length; i++) {
const set = new Set();
for (let j = i; j < nums.length; j++) {
set.add(nums[j]);
res += set.size ** 2;
}
}
return res;
};