Subarrays Distinct Element Sum of Squares I - Video Solutions

Problem 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.