Subarrays Distinct Element Sum of Squares I

Difficulty: Easy | Acceptance: 80.10% | Paid: No Topics: Array, Hash Table

You are given a 0-indexed integer array nums.

The distinct count of a subarray of nums is defined as the number of distinct integers in that subarray.

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

A subarray is defined as a non-empty contiguous sequence of elements in the array.

• Examples
• Constraints
• Brute Force with Hash Set
• Boolean Array Optimization

Examples

Input: nums = [1,2,1]
Output: 15
Explanation: Six subarrays:
- [1]: distinct count is 1, square is 1
- [1,2]: distinct count is 2, square is 4
- [1,2,1]: distinct count is 2, square is 4
- [2]: distinct count is 1, square is 1
- [2,1]: distinct count is 2, square is 4
- [1]: distinct count is 1, square is 1
Sum of squares = 1 + 4 + 4 + 1 + 4 + 1 = 15

Input: nums = [2,2]
Output: 3
Explanation: Three subarrays:
- [2]: distinct count is 1, square is 1
- [2,2]: distinct count is 1, square is 1
- [2]: distinct count is 1, square is 1
Sum of squares = 1 + 1 + 1 = 3

Constraints

1 <= nums.length <= 100
1 <= nums[i] <= 100

Brute Force with Hash Set

Intuition Generate all subarrays and use a hash set to track distinct elements, squaring the count for each subarray.

Steps

• Iterate through all starting positions of subarrays
• For each start, expand the subarray and maintain a set of seen elements
• Add the square of the set size to the result for each expansion

from typing import List

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

Complexity

• Time: O(n²)
• Space: O(n)
• Notes: Each element is added to a set exactly once per starting position, making this efficient for the given constraints.

Boolean Array Optimization

Intuition Since values are bounded (1 to 100), use a boolean array instead of a hash set for faster lookups and better cache locality.

Steps

• Iterate through all starting positions
• Use a fixed-size boolean array to track seen elements
• Maintain a running count of distinct elements to avoid recalculating

from typing import List

class Solution:
    def sumCounts(self, nums: List[int]) -> int:
        n = len(nums)
        result = 0
        for i in range(n):
            seen = [False] * 101
            count = 0
            for j in range(i, n):
                if not seen[nums[j]]:
                    seen[nums[j]] = True
                    count += 1
                result += count * count
        return result

Complexity

• Time: O(n²)
• Space: O(1) - fixed size array regardless of input
• Notes: Better constant factors than hash set approach due to direct array indexing and no hashing overhead.