← All solutions
October 15Easy

Subarrays distinct element sum of squares i

  • Array
  • Hash Table

Problem

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. A subarray is a contiguous non-empty sequence of elements within an array.

Solution

class Solution:
    def sumCounts(self, nums: List[int]) -> int:
        n = len(nums)
        ans = 0
        for i in range(0, n):
            freq = set()
            for j in range(i, n):
                freq.add(nums[j])
                ans += len(freq) ** 2
        return ans