Introduction
Some array problems ask for the sum of elements, while others require counting unique values inside different portions of an array. LeetCode 2913 combines both ideas: every possible subarray must be considered, its distinct elements counted, and that count squared before being added to the final answer.
The interesting part is that two solutions can perform the same calculations in slightly different ways. One approach stores the distinct count of each subarray and calculates the squares in a separate pass. The other calculates each square immediately after updating the set of distinct elements.
The second approach avoids storing intermediate counts and makes the implementation more direct.
In this article, both approaches are explained using Java, including the role of HashSet, a dry run of the example, complexity analysis, and the difference between the two implementations.
Problem Statement
In LeetCode 2913 – Subarrays Distinct Element Sum of Squares I, an integer array nums is given.
For every non-empty contiguous subarray, find the number of distinct elements, square that number, and add it to the total.
A subarray is a contiguous sequence of elements from the original array.
Mathematically, if (d(s)) represents the number of distinct values in a subarray (s), the required answer is:
Formula: Sum of (distinct element count × distinct element count) for every non-empty subarray
Example 1
The six possible subarrays are:
| Subarray | Distinct elements | Distinct count squared |
[1] | {1} | (1^2=1) |
[2] | {2} | (1^2=1) |
[1] | {1} | (1^2=1) |
[1, 2] | {1, 2} | (2^2=4) |
[2, 1] | {1, 2} | (2^2=4) |
[1, 2, 1] | {1, 2} | (2^2=4) |
Adding the contributions gives:
1+1+1+4+4+4=15
Notice that repeated values are counted only once within a subarray. For example, [1, 2, 1] has three elements but only two distinct values.
Example 2
The possible subarrays are [1], [1], and [1, 1].
Each has exactly one distinct value, so the answer is:
1^2+1^2+1^2=3
Approach 1: Store Distinct Counts and Calculate the Squares Later
The first approach follows the problem statement directly.
For every starting index, all subarrays beginning at that index are explored. A HashSet keeps track of the unique values encountered as the ending index moves forward.
Whenever a new element is added, the size of the set represents the number of distinct values in the current subarray.
Instead of calculating the square immediately, this approach stores each distinct count in a list. After all subarrays have been processed, another loop squares the stored counts and adds them to the answer.
Java Code
How It Works
- Choose a starting index
i. - Create an empty
HashSetfor that starting position. - Move the ending index
jforward, adding each element to the set. - Store
set.size()for every subarray. - After processing all subarrays, square each stored count and add it to
sum.
This approach is easy to understand because it separates the two operations: finding distinct counts and calculating their squared contributions.
However, it stores a value for every subarray, even though each count can be used immediately.
Approach 2: Calculate Each Square Directly
The second approach simplifies the process by calculating each contribution as soon as the distinct count is known.
Instead of storing the counts in another list, the code adds the square directly to the running total.
This is the approach used in the submitted solution.
Java Code
Why Does sum Start at arr.size()?
This line is an important detail:
Every individual element forms a subarray of length one.
For a single-element subarray such as [5], the number of distinct values is always one, so its contribution is:
1^2=1
An array of length (n) has exactly (n) single-element subarrays. Their total contribution is therefore (n).
That is why the code initializes sum to arr.size().
The outer loop then handles the remaining subarrays, which have lengths of at least two.
Why Use a HashSet?
Consider the array:
As the ending index moves forward, the set changes like this:
| Current subarray | Set contents | Distinct count |
[1, 2] | {1, 2} | 2 |
[1, 2, 1] | {1, 2} | 2 |
Adding the second occurrence of 1 does not increase the set size. A HashSet automatically ignores duplicate values, so ms.size() always provides the correct distinct count.
The code then immediately adds:
This removes the need for a separate list and a final traversal.
Dry Run of the Improved Approach
Let's trace the submitted solution with:
Initially:
The initial value accounts for the three single-element subarrays:
Each contributes one, giving a total of three.
First starting index: i = 0
The set begins with the first element:
The inner loop starts at j = 1.
j | Current subarray | Set | Distinct count | Added contribution |
| 1 | [1, 2] | {1, 2} | 2 | (2^2=4) |
| 2 | [1, 2, 1] | {1, 2} | 2 | (2^2=4) |
Running total:
Second starting index: i = 1
The set starts again with the element at index one:
The inner loop continues from j = 2.
j | Current subarray | Set | Distinct count | Added contribution |
| 2 | [2, 1] | {1, 2} | 2 | (2^2=4) |
Running total:
Third starting index: i = 2
There are no elements after the starting index, so the inner loop does not execute.
The contribution of [1] was already included in the initial value of sum.
Final result:
All six subarrays have been accounted for.
Comparing the Two Approaches
Both approaches enumerate the same set of subarrays and use a HashSet to count distinct elements. The difference is how the contributions are accumulated.
| Feature | Approach 1 | Approach 2 |
| Counts distinct elements | HashSet | HashSet |
| Stores counts separately | Yes | No |
| Calculates squares | In a second loop | Immediately |
| Extra storage for counts | (O(n^2)) | None beyond the set |
| Overall time complexity | (O(n^2)) expected | (O(n^2)) expected |
| Implementation | Two phases | One accumulation phase |
The second approach is more space-efficient because it does not store a separate count for every subarray.
It is important to distinguish this improvement from a change in asymptotic time complexity. Both approaches still examine a quadratic number of subarrays, so the direct-calculation version is not an (O(n)) solution.
Complexity Analysis
Let (n) be the length of the input array.
Time Complexity: (O(n^2)) expected
There are (n(n+1)/2) non-empty subarrays.
The nested loops enumerate these subarrays, and the HashSet performs insertions in expected constant time under normal hashing assumptions.
Therefore, the overall expected time complexity is:
O(n^2)
Space Complexity
Approach 1: (O(n^2)) auxiliary space for the list of stored distinct counts, plus the set used during enumeration.
Approach 2: (O(n)) auxiliary space in the worst case for the HashSet, since it can contain up to (n) distinct values. No separate list of counts is needed.
With the given constraint (n\leq100), the straightforward nested-loop approach is suitable.
Interview Tip: Avoid Storing Values You Can Use Immediately
A useful optimization habit is to ask whether an intermediate result needs to be saved.
In the first approach, each distinct count is stored because the squares are calculated later. But the count is already available at the moment the subarray is processed.
That makes this operation possible:
The general lesson is not that a separate list is always wrong. It is that intermediate storage should serve a purpose. If a value can be consumed immediately, doing so may simplify the code and reduce memory usage.
For this problem, the main algorithm remains the same: enumerate every subarray, maintain its distinct values, and add the square of the current distinct count.
Conclusion
LeetCode 2913 is a useful exercise in subarray enumeration and distinct-element counting. The HashSet handles duplicate values, while nested loops ensure that every non-empty contiguous subarray is considered.
The first approach stores the distinct count of each subarray and calculates the squares afterward. The second approach, used in the submitted solution, adds each squared count immediately.
Both approaches have expected (O(n^2)) time complexity, but the second uses less auxiliary space and keeps the calculation in one place.
For small constraints like those in this problem, a clear and correct brute-force solution is often the right choice. Understanding why the direct-calculation version is simpler is also a useful step toward writing more concise and memory-conscious Java code.
