Subarrays Distinct Element Sum of Squares I solution and explanation
Google
5 more videos on this problem
Subarrays Distinct Element Sum of Squares I |Biweekly Contest 116 | Leetcode | DCC NIT-ADCC NITA · 10:50 · 818 views
2913. Subarrays Distinct Element Sum of Squares I (Leetcode Easy)Programming Live with Larry · 4:18 · 632 views
100094. Subarrays Distinct Element Sum of Squares I | Leetcode Biweekly Contest 116.Optimization · 0:10 · 550 views
2913. Subarrays Distinct Element Sum of Squares I | Leetcode Biweekly 116 | C++Code Adore · 2:58 · 464 views
2913. Subarrays Distinct Element Sum of Squares I - JavaScriptSofia Bargues · 3:38 · 21 views
Leetcode Biweekly-Contest116 |Subarrays Distinct Element Sum of Squares ICreator_AB · 0:55 · 11 views
The problem
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 ofnumsconsisting of all the indices fromitojsuch that0 <= i <= j < nums.length. Then the number of distinct values innums[i..j]is called the distinct count ofnums[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] <= 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.
def sum_of_distinct_squares(nums):
total = 0
n = len(nums)
for i in range(n):
distinct = set()
for j in range(i, n):
distinct.add(nums[j])
distinct_count = len(distinct)
total += distinct_count ** 2
return total
nums = [1, 2, 1]
print(sum_of_distinct_squares(nums))import java.util.HashSet;
public class Solution {
public int sumOfDistinctSquares(int[] nums) {
int total = 0;
for (int i = 0; i < nums.length; i++) {
HashSet<Integer> distinctSet = new HashSet<>();
for (int j = i; j < nums.length; j++) {
distinctSet.add(nums[j]);
int distinctCount = distinctSet.size();
total += distinctCount * distinctCount;
}
}
return total;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {1, 2, 1};
System.out.println(sol.sumOfDistinctSquares(nums));
}
}#include <iostream>
#include <vector>
#include <unordered_set>
int sumOfDistinctSquares(std::vector<int>& nums) {
int total = 0;
int n = nums.size();
for (int i = 0; i < n; ++i) {
std::unordered_set<int> distinctSet;
for (int j = i; j < n; ++j) {
distinctSet.insert(nums[j]);
int distinctCount = distinctSet.size();
total += distinctCount * distinctCount;
}
}
return total;
}
int main() {
std::vector<int> nums = {1, 2, 1};
std::cout << sumOfDistinctSquares(nums) << std::endl;
return 0;
}function sumOfDistinctSquares(nums) {
let total = 0;
for (let i = 0; i < nums.length; i++) {
let distinctSet = new Set();
for (let j = i; j < nums.length; j++) {
distinctSet.add(nums[j]);
const distinctCount = distinctSet.size;
total += distinctCount * distinctCount;
}
}
return total;
}
let nums = [1, 2, 1];
console.log(sumOfDistinctSquares(nums));#include <stdio.h>
#include <string.h>
int sumOfDistinctSquares(int* nums, int numsSize) {
int total = 0;
for (int i = 0; i < numsSize; i++) {
int count[101] = {0};
int distinctCount = 0;
for (int j = i; j < numsSize; j++) {
if (count[nums[j]] == 0) {
distinctCount++;
}
count[nums[j]]++;
total += distinctCount * distinctCount;
}
}
return total;
}
int main() {
int nums[] = {1, 2, 1};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", sumOfDistinctSquares(nums, size));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int SumOfDistinctSquares(int[] nums) {
int total = 0;
for (int i = 0; i < nums.Length; i++) {
HashSet<int> distinctSet = new HashSet<int>();
for (int j = i; j < nums.Length; j++) {
distinctSet.Add(nums[j]);
int distinctCount = distinctSet.Count;
total += distinctCount * distinctCount;
}
}
return total;
}
public static void Main(string[] args) {
Solution sol = new Solution();
int[] nums = {1, 2, 1};
Console.WriteLine(sol.SumOfDistinctSquares(nums));
}
}Generates subarrays starting from each index and maintains a set to store distinct elements, computing squares of distinct count for each.
Overall time complexity is O(n^3), and space complexity is O(n) due to the use of a set for distinct tracking.
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.
def sum_of_distinct_squares(nums):
total = 0
n = len(nums)
for left in range(n):
count_map = {}
distinct_count = 0
for right in range(left, n):
if nums[right] not in count_map:
count_map[nums[right]] = 0
count_map[nums[right]] += 1
if count_map[nums[right]] == 1:
distinct_count += 1
total += distinct_count ** 2
return total
nums = [1, 2, 1]
print(sum_of_distinct_squares(nums))import java.util.HashMap;
public class Solution {
public int sumOfDistinctSquares(int[] nums) {
int total = 0;
for (int left = 0; left < nums.length; left++) {
HashMap<Integer, Integer> countMap = new HashMap<>();
int distinctCount = 0;
for (int right = left; right < nums.length; right++) {
countMap.put(nums[right], countMap.getOrDefault(nums[right], 0) + 1);
if (countMap.get(nums[right]) == 1) distinctCount++;
total += distinctCount * distinctCount;
}
}
return total;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {1, 2, 1};
System.out.println(sol.sumOfDistinctSquares(nums));
}
}#include <iostream>
#include <vector>
#include <unordered_map>
int sumOfDistinctSquares(std::vector<int>& nums) {
int total = 0;
int n = nums.size();
for (int left = 0; left < n; ++left) {
std::unordered_map<int, int> countMap;
int distinct_count = 0;
for (int right = left; right < n; ++right) {
if (++countMap[nums[right]] == 1) {
++distinct_count;
}
total += distinct_count * distinct_count;
}
}
return total;
}
int main() {
std::vector<int> nums = {1, 2, 1};
std::cout << sumOfDistinctSquares(nums) << std::endl;
return 0;
}function sumOfDistinctSquares(nums) {
let total = 0;
for (let left = 0; left < nums.length; left++) {
let countMap = {};
let distinctCount = 0;
for (let right = left; right < nums.length; right++) {
if (!countMap[nums[right]]) {
countMap[nums[right]] = 0;
}
if (++countMap[nums[right]] === 1) {
distinctCount++;
}
total += distinctCount * distinctCount;
}
}
return total;
}
let nums = [1, 2, 1];
console.log(sumOfDistinctSquares(nums));#include <stdio.h>
#include <string.h>
int sumOfDistinctSquares(int* nums, int numsSize) {
int total = 0;
for (int left = 0; left < numsSize; left++) {
int count[101] = {0};
int distinct_count = 0;
for (int right = left; right < numsSize; right++) {
if (count[nums[right]] == 0) distinct_count++;
count[nums[right]]++;
total += distinct_count * distinct_count;
}
}
return total;
}
int main() {
int nums[] = {1, 2, 1};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", sumOfDistinctSquares(nums, size));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int SumOfDistinctSquares(int[] nums) {
int total = 0;
for (int left = 0; left < nums.Length; left++) {
Dictionary<int, int> countMap = new Dictionary<int, int>();
int distinctCount = 0;
for (int right = left; right < nums.Length; right++) {
if (!countMap.ContainsKey(nums[right])) {
countMap[nums[right]] = 0;
}
countMap[nums[right]]++;
if (countMap[nums[right]] == 1) {
distinctCount++;
}
total += distinctCount * distinctCount;
}
}
return total;
}
public static void Main(string[] args) {
Solution sol = new Solution();
int[] nums = {1, 2, 1};
Console.WriteLine(sol.SumOfDistinctSquares(nums));
}
}Python's dictionary structures efficiently track elements' occurrences, enabling faster recomputing of distinct counts while exploring subarrays rather than recalculating from zero each time.
Time complexity of O(n^2) and space complexity of O(n) due to using a dictionary for element frequency.
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.
function sumCounts(nums: number[]): number {
let ans = 0;
const n = nums.length;
for (let i = 0; i < n; ++i) {
const s: number[] = Array(101).fill(0);
let cnt = 0;
for (const x of nums.slice(i)) {
if (++s[x] === 1) {
++cnt;
}
ans += cnt * cnt;
}
}
return ans;
}func sumCounts(nums []int) (ans int) {
for i := range nums {
s := [101]int{}
cnt := 0
for _, x := range nums[i:] {
s[x]++
if s[x] == 1 {
cnt++
}
ans += cnt * cnt
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Overall time complexity is O(n^3), and space complexity is O(n) due to the use of a set for distinct tracking. |
| Optimized Sliding Window Approach | Time complexity of O(n^2) and space complexity of O(n) due to using a dictionary for element frequency. |
| Enumeration | – |
Complexity analysis
| 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 |
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.