You are given a 0-indexed integer array nums.
The distinct count of a subarray of nums is defined as:
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.
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] <= 100Problem Overview: Given an array nums, evaluate every possible subarray. For each subarray, count how many distinct elements it contains, square that count, and add it to the final total. The challenge is efficiently tracking distinct elements while iterating through all subarrays.
Approach 1: Brute Force with Recomputed Set (O(n^3) time, O(n) space)
Start every subarray at index i and extend it to j. For each pair (i, j), rebuild a set of elements in that subarray to compute the number of distinct values. The square of the set size contributes to the answer. This method repeatedly scans the same elements, which leads to O(n^3) time: two loops for the subarray boundaries and another pass to count distinct elements. Space usage is O(n) for the temporary set. It works for small inputs but wastes work by recomputing distinct counts from scratch.
Approach 2: Incremental Sliding Window with Hash Map (O(n^2) time, O(n) space)
Fix the starting index i and expand the right boundary j. Maintain a frequency map using a hash table. When adding nums[j], update its count and track whether it introduces a new distinct value. The distinct count can now be updated in constant time instead of recomputed. Each expansion contributes distinct_count * distinct_count to the answer. This eliminates the inner recomputation loop and reduces complexity to O(n^2) with O(n) space for the frequency map.
This pattern resembles a sliding window, where the window expands while maintaining element frequencies. However, because every possible start index must be evaluated, the window is restarted for each i. The approach still dramatically improves performance compared with naive recomputation.
Arrays with repeated elements benefit the most from this optimization because the frequency map immediately reveals whether a value increases the distinct count.
Recommended for interviews: Start by explaining the brute force idea to demonstrate understanding of subarrays and distinct counting. Then move to the optimized hash map approach. Interviewers expect the O(n^2) incremental counting technique using a frequency map from the array. It avoids redundant work and shows you understand how to maintain dynamic state while expanding a subarray.
The brute force approach involves generating all possible subarrays of the given array and calculating the distinct element count for each subarray. Then, compute the square of each distinct count and add them all up. This naive solution works due to the constraints given, with small array lengths.
The solution generates each possible subarray starting from every index, then checks for the distinct count by using an auxiliary array. We then sum up the squares of these distinct counts for each subarray.
The time complexity is O(n^3) due to the nested loops, and the space complexity is O(1), disregarding input storage.
This approach optimizes the naive method using a sliding window. By using two pointers and a frequency map, we can maintain the distinct count as elements are added or removed as the window slides. This reduces the need to recalculate from scratch for every subarray.
This solution uses two nested loops, but it keeps track of the distinct counts using an integer array and counts all distinct number frequencies within a logical sliding window.
The time complexity is O(n^2), as it reduces the overhead of redundant checks compared to the previous approach. The space complexity is O(1) excluding input storage.
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.
After the enumeration, we return the answer.
The time complexity is O(n^2), and the space complexity is O(n). Here, n is the length of the array nums.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Brute Force Approach | The time complexity is O(n^3) due to the nested loops, and the space complexity is O(1), disregarding input storage. |
| Optimized Sliding Window Approach | The time complexity is O(n^2), as it reduces the overhead of redundant checks compared to the previous approach. The space complexity is O(1) excluding input storage. |
| Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Set Recalculation | O(n^3) | O(n) | Conceptual baseline or very small arrays where simplicity matters more than efficiency |
| Incremental Hash Map / Sliding Window Expansion | O(n^2) | O(n) | General case. Maintains frequency counts while expanding subarrays to avoid recomputing distinct elements |
Subarrays Distinct Element Sum of Squares I |Biweekly Contest 116 | Leetcode | DCC NIT-A • DCC NITA • 812 views views
Watch 4 more video solutions →Practice Subarrays Distinct Element Sum of Squares I with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor