Skip to main content
Talentd

Subarrays Distinct Element Sum of Squares I - Solution & Explanation

EasyArrayHash Table15 min readAsked at: Google
Practice this problem

Problem Statement

You are given a 0-indexed integer array nums.

The distinct count of a subarray of nums is defined as:

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

Approach Overview

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.

Approach 1: Brute Force Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

The time complexity is O(n^3) due to the nested loops, and the space complexity is O(1), disregarding input storage.

Try this approach in the editor →

Approach 2: Optimized Sliding Window Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: 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.

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force with Set RecalculationO(n^3)O(n)Conceptual baseline or very small arrays where simplicity matters more than efficiency
Incremental Hash Map / Sliding Window ExpansionO(n^2)O(n)General case. Maintains frequency counts while expanding subarrays to avoid recomputing distinct elements

Video Solution

Subarrays Distinct Element Sum of Squares I |Biweekly Contest 116 | Leetcode | DCC NIT-A • DCC NITA • 818 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Subarrays Distinct Element Sum of Squares I easy or hard?
LeetCode classifies this problem as Easy. The main idea is straightforward: iterate over all subarrays and track distinct elements. The optimization with a hash map reduces redundant work and is commonly expected in interviews.
Subarrays Distinct Element Sum of Squares I Python/Java solution
The typical implementation uses nested loops and a dictionary or hash map. For each starting index, create a frequency map and extend the subarray while updating counts and the number of distinct elements. The square of the distinct count is added to the result at every step. The same logic translates directly across Python, Java, C++, and other languages.
How to solve Subarrays Distinct Element Sum of Squares I in O(n)?
An O(n) solution is not possible because the number of subarrays in an array of length n is n(n+1)/2. Each subarray contributes to the final sum, so at least O(n^2) work is required to evaluate them. The optimal approach therefore maintains distinct counts incrementally and achieves O(n^2) time with a hash map.
What is the best approach for Subarrays Distinct Element Sum of Squares I?
The most practical solution uses an incremental hash map while expanding each subarray. Fix a starting index, extend the right boundary, and maintain element frequencies in a hash table. The number of distinct elements can be updated in O(1), so each extension contributes distinct_count^2 to the total. This reduces the complexity to O(n^2) time and O(n) space.
Is Subarrays Distinct Element Sum of Squares I asked at Google/Amazon/Meta?
Problems involving subarrays, distinct element counting, and hash table frequency tracking are common in interviews at companies like Amazon, Google, and Meta. This exact problem may appear in online assessments or practice sets because it tests understanding of arrays, hash maps, and incremental window expansion.
What data structure is used in Subarrays Distinct Element Sum of Squares I?
A hash table (or dictionary/map) is used to store the frequency of elements in the current subarray. The map allows constant-time updates when extending the subarray and quickly determines whether an element increases the distinct count.
What is the time complexity of Subarrays Distinct Element Sum of Squares I?
The optimized solution runs in O(n^2) time because every subarray start index expands through the remaining elements once. Distinct counts are updated using a hash table in constant time. Space complexity is O(n) for the frequency map that tracks element counts.

Ready to solve this problem?

Practice Subarrays Distinct Element Sum of Squares I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays