#2913

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Subarrays Distinct Element Sum of Squares I

Compute the sum of squares of distinct elements for all subarrays using array scanning with hash lookups efficiently.

Problem Statement

You are given a 0-indexed integer array nums. Each subarray's distinct element count is the number of unique values it contains. Your task is to sum the squares of these counts across all possible subarrays.

Return a single integer representing the sum of the squares of the distinct element counts of every subarray of nums. For example, nums = [1,2,1] has subarrays [1], [2], [1], [1,2], [2,1], [1,2,1], and the sum of their squared distinct counts equals 15.

Examples

Example 1

Input: nums = [1,2,1]

Output: 15

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

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 <= 100
1 <= nums[i] <= 100

Solution Approach

Brute Force with Hash Set

Iterate over all subarrays and use a hash set to track distinct elements. Compute the count of each subarray, square it, and accumulate the sum. This directly follows the array scanning plus hash lookup pattern but may be inefficient for larger arrays.

Optimized Sliding Window

Use a sliding window to expand subarrays while maintaining a hash map of element frequencies. This avoids redundant recalculations and efficiently counts distinct elements. The sum of squares is updated incrementally as the window moves.

Precompute Distinct Contributions

For each element, determine how many subarrays include it as a distinct element and contribute to the square sum. Multiply contributions by the element's presence count in subarrays, summing all results. This reduces nested iterations while using hash-based tracking.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity ranges from O(n^2) for brute-force to O(n)–O(n^2) depending on sliding window optimizations. Space complexity is O(n) for hash sets or hash maps used to track distinct elements.

What Interviewers Usually Probe

Asks about counting distinct elements efficiently within subarrays.
Mentions using a set or hash map during array traversal.
Checks if you can optimize nested loops with incremental counting.

Common Pitfalls or Variants

Common pitfalls

Double-counting elements when expanding subarrays without proper hash tracking.
Forgetting to square the distinct counts before summing.
Assuming all elements are unique without handling duplicates.

Follow-up variants

Sum of cubes of distinct element counts instead of squares.
Compute distinct counts only for subarrays of fixed length.
Count distinct element contributions modulo a large prime for large arrays.

FAQ

What is the main pattern used in Subarrays Distinct Element Sum of Squares I?

The problem follows the Array scanning plus hash lookup pattern, where a hash set tracks distinct elements efficiently.

How do I handle duplicates when computing distinct counts?

Use a hash map to maintain frequencies, ensuring each unique element is counted once per subarray.

Can this be solved faster than O(n^2)?

Sliding window and precomputed contribution approaches can reduce redundant counting, potentially improving practical performance.

What is the expected output for nums = [1,2,1]?

The sum of squares of distinct counts for all subarrays is 15, calculated from [1], [2], [1], [1,2], [2,1], [1,2,1].

Why use a hash set instead of a simple array for tracking?

A hash set dynamically handles distinct element presence regardless of values and avoids manual counting or index mapping.

terminal

Solution

Solution 1: Enumeration

We can enumerate the left endpoint index $i$ of the subarray, and for each $i$, we enumerate the right endpoint index $j$ in the range $[i, n)$, and calculate the distinct count of $nums[i..j]$ by adding the count of $nums[j]$ to a set $s$, and then taking the square of the size of $s$ as the contribution of $nums[i..j]$ to the answer.

1

2

3

4

5

6

7

8

9

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

Continue Practicing

#2910 minimum number of groups to create a valid assignment #2902 count of sub multisets with bounded sum #2897 apply operations on array to maximize sum of squares