Subarrays Distinct Element Sum of Squares I

Easy
1808.

Subarrays Distinct Element Sum of Squares I

Subarrays Distinct Element Sum of Squares I is an easy coding problem on arrays and hash table, asked in Amazon interviews.

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 <= 100
  • 1 <= nums[i] <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var sumCounts = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

Hints for Subarrays Distinct Element Sum of Squares I

  1. Hint 1

    With at most 100 elements there are only about 5,000 subarrays.

  2. Hint 2

    Fix the left end and extend to the right; a value seen for the first time raises the distinct count by one.

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

  1. For each i, clear seen[0..100] and set distinct = 0.
  2. For each j >= i: if nums[j] is unseen, mark it and increment distinct.
  3. Add distinct^2 to 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 total

Java

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