Subarrays Distinct Element Sum of Squares I

Subarrays Distinct Element Sum of Squares I - 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 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.

Input & Output

Example 1 — Basic Case

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

› Output: 15

💡 Note: Subarrays: [1]→1²=1, [1,2]→2²=4, [1,2,1]→2²=4, [2]→1²=1, [2,1]→2²=4, [1]→1²=1. Sum = 1+4+4+1+4+1 = 15

Example 2 — All Same Elements

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

› Output: 6

💡 Note: All subarrays have distinct count 1: [1]→1, [1,1]→1, [1,1,1]→1, [1]→1, [1,1]→1, [1]→1. Sum = 6×1² = 6

Example 3 — All Different Elements

$ Input: nums = [1,2]

› Output: 6

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

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array [1,2,1]

Find Subarrays

Generate all contiguous subarrays and count distinct elements

Sum Squares

Square each distinct count and sum all results

Key Takeaway

🎯 Key Insight: Generate all subarrays, count distinct elements using a set, square each count, and sum the results

Asked in

G Google 15 M Microsoft 12

The key insight is to generate all possible subarrays and count distinct elements in each, then square the counts and sum them. The optimized approach extends subarrays incrementally from each starting position to avoid redundant work. Time: O(n²), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Subarrays	O(n³)	O(n)	Generate all possible subarrays and count distinct elements in each
Optimized - Extend Subarrays	O(n²)	O(n)	For each starting position, incrementally build subarrays and track distinct elements

Brute Force - Check All Subarrays — Algorithm Steps

For each starting index i
For each ending index j >= i
Count distinct elements in subarray [i,j]
Square the count and add to result

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subarrays

Create all possible contiguous subarrays

Count Distinct

Use set to count unique elements in each subarray

Square & Sum

Square each count and add to total

Code -

solution.c — C

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

int solution(int* nums, int numsSize) {
    int result = 0;
    
    // Check all possible subarrays
    for (int i = 0; i < numsSize; i++) {
        for (int j = i; j < numsSize; j++) {
            // Count distinct elements in subarray [i, j]
            int distinct[1001] = {0}; // Assuming values in range [0, 1000]
            int count = 0;
            
            for (int k = i; k <= j; k++) {
                int val = nums[k] + 500; // Shift for negative values
                if (!distinct[val]) {
                    distinct[val] = 1;
                    count++;
                }
            }
            
            // Square the count and add to result
            result += count * count;
        }
    }
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int size = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            nums[size++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(nums, size);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Two nested loops for all subarrays O(n²), and counting distinct elements takes O(n) for each subarray

⚠ Quadratic Growth

Space Complexity

O(n)

Set to store distinct elements for each subarray, maximum n elements

⚡ Linearithmic Space

8.5K Views

Medium Frequency

~15 min Avg. Time

234 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

Brute Force - Check All Subarrays — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler