Subarrays Distinct Element Sum of Squares II

Subarrays Distinct Element Sum of Squares II - Problem

You are given a 0-indexed integer array nums. The distinct count of a subarray is defined as follows:

Let nums[i..j] be a subarray of nums consisting of all indices from i to j such that 0 <= i <= j < nums.length. The number of distinct values in nums[i..j] is called the distinct count of nums[i..j].

Return the sum of squares of distinct counts of all subarrays of nums. Since the answer may be very large, return it modulo 10^9 + 7.

A subarray is a contiguous non-empty sequence of elements within an array.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,1]

› Output: 15

💡 Note: All subarrays: [1](1²=1), [2](1²=1), [1](1²=1), [1,2](2²=4), [2,1](2²=4), [1,2,1](2²=4). Sum = 1+1+1+4+4+4 = 15

Example 2 — All Different

$ Input: nums = [1,2]

› Output: 6

💡 Note: Subarrays: [1](1²=1), [2](1²=1), [1,2](2²=4). Sum = 1+1+4 = 6

Example 3 — Single Element

$ Input: nums = [5]

› Output: 1

💡 Note: Only one subarray [5] with 1 distinct element: 1² = 1

Constraints

1 ≤ nums.length ≤ 100
1 ≤ nums[i] ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array with possible duplicate elements

Generate Subarrays

Find all contiguous subarrays and count distinct elements

Square and Sum

Square each distinct count and sum all results

Key Takeaway

🎯 Key Insight: Count distinct elements efficiently in all subarrays and sum their squares

Asked in

G Google 25 M Microsoft 20 a Amazon 15

The key insight is to efficiently count distinct elements in all subarrays. The optimized approach uses incremental set building to avoid redundant counting. Best approach has Time: O(n²), Space: O(n) using sets for distinct element tracking.

Common Approaches

Approach	Time	Space	Notes
✓ Optimized with Set Tracking	O(n²)	O(n)	Use incremental set building to avoid recounting distinct elements
Brute Force	O(n³)	O(n)	Check all subarrays and count distinct elements using sets

Optimized with Set Tracking — Algorithm Steps

For each starting position i
Incrementally extend subarray to position j
Add new element to set and square the current distinct count

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Position

Begin with empty set at each starting index

Extend Right

Add elements to set as we extend subarray

Track Contribution

Square distinct count at each step

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize) {
    const int MOD = 1000000007;
    long long total = 0;
    
    for (int i = 0; i < numsSize; i++) {
        int distinct[1001] = {0};
        int distinctCount = 0;
        
        for (int j = i; j < numsSize; j++) {
            if (distinct[nums[j] + 500] == 0) {
                distinct[nums[j] + 500] = 1;
                distinctCount++;
            }
            
            total = (total + (long long)distinctCount * distinctCount) % MOD;
        }
    }
    
    return (int)total;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, numsSize);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Two nested loops to generate all subarrays, O(1) set operations

⚠ Quadratic Growth

Space Complexity

O(n)

Set to store distinct elements for current subarray

⚡ Linearithmic Space

24.9K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized with Set Tracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler