Subarrays Distinct Element Sum of Squares I — Solution
Subarrays Distinct Element Sum of Squares I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Subarrays Distinct Element Sum of Squares I is an easy coding problem on arrays and hash table, asked in Amazon interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an integer array nums. The distinct count of a subarray is the number of different values it contains.
Return the sum of the squares of the distinct counts of all non-empty contiguous subarrays of nums.
Example 1
Input: nums = [1,2,1]
Output: 15
Explanation: The six subarrays have distinct counts 1, 1, 1, 2, 2, 2, so the sum is `3 · 1 + 3 · 4 = 15`.
Example 2
Input: nums = [1,1]
Output: 3
Explanation: `[1]`, `[1]` and `[1,1]` each have one distinct value.
Example 3
Input: nums = [7]
Output: 1
Constraints
1 <= nums.length <= 1001 <= nums[i] <= 100
Hints for Subarrays Distinct Element Sum of Squares I
Hint 1
With at most 100 elements there are only about 5,000 subarrays.
Hint 2
Fix the left end and extend to the right; a value seen for the first time raises the distinct count by one.
Hint 3
Values are at most 100, so a boolean array of size 101 (cleared for each left end) tracks what has been seen.
How to solve Subarrays Distinct Element Sum of Squares I
For each left end, grow the subarray one element at a time and keep the number of distinct values with a small seen table; add its square for every right end.
Approach
- For each
i, clearseen[0..100]and setdistinct = 0. - For each
j >= i: ifnums[j]is unseen, mark it and incrementdistinct. - Add
distinct^2to the total.
Why it works
Each subarray nums[i..j] is visited exactly once, and at that moment distinct equals the number of values marked, which are exactly the values of nums[i..j].
Complexity
- Time —
O(n^2) - Space —
O(V) with V = 100
Pitfalls
- Recounting each subarray from scratch costs an extra factor of
n— fine here, but the incremental count is just as short. - Square the distinct count, not the subarray length.
Reference solution
Python
from typing import List
def sumCounts(nums: List[int]) -> int:
n = len(nums)
total = 0
for i in range(n):
seen = [False] * 101
distinct = 0
for j in range(i, n):
if not seen[nums[j]]:
seen[nums[j]] = True
distinct += 1
total += distinct * distinct
return totalJava
public static int sumCounts(int[] nums) {
int n = nums.length;
int total = 0;
for (int i = 0; i < n; i++) {
boolean[] seen = new boolean[101];
int distinct = 0;
for (int j = i; j < n; j++) {
if (!seen[nums[j]]) { seen[nums[j]] = true; distinct++; }
total += distinct * distinct;
}
}
return total;
}C++
int sumCounts(vector<int>& nums) {
int n = nums.size();
int total = 0;
for (int i = 0; i < n; i++) {
bool seen[101] = {false};
int distinct = 0;
for (int j = i; j < n; j++) {
if (!seen[nums[j]]) { seen[nums[j]] = true; distinct++; }
total += distinct * distinct;
}
}
return total;
}JavaScript
var sumCounts = function(nums) {
var n = nums.length;
var total = 0;
var seen = new Uint8Array(101);
for (var i = 0; i < n; i++) {
seen.fill(0);
var distinct = 0;
for (var j = i; j < n; j++) {
if (!seen[nums[j]]) { seen[nums[j]] = 1; distinct++; }
total += distinct * distinct;
}
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets