Scale Engineer

Subarrays Distinct Element Sum of Squares I

Easy
#2594Time: O(N^3), where N is the length of `nums`. There are three nested loops. The outer two loops select a subarray (O(N^2) subarrays), and the inner loop iterates through the subarray's elements (up to O(N) elements), leading to a cubic time complexity.Space: O(N), where N is the length of `nums`. The `HashSet` can store up to N distinct elements in the worst case for a single subarray.
Data structures
ArrayHash Table

Prompt

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.

 

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach is the most straightforward and directly follows the problem description. It involves generating every possible subarray of the input array nums. For each of these subarrays, we iterate through its elements to count the number of distinct values using a HashSet. Finally, we square this count and add it to a running total.

Algorithm

  • Initialize a variable totalSum to 0.
  • Use a pair of nested loops with indices i and j to generate all possible subarrays. The outer loop i runs from 0 to n-1 (start index), and the inner loop j runs from i to n-1 (end index).
  • For each subarray nums[i..j], create a new HashSet to store its unique elements.
  • Use a third nested loop with index k from i to j to iterate through the current subarray.
  • Add each element nums[k] to the HashSet.
  • After iterating through the subarray, the size of the HashSet gives the count of distinct elements.
  • Square this count and add it to totalSum.
  • After all subarrays have been processed, return totalSum.

Walkthrough

The algorithm employs three nested loops. The first two loops, with indices i and j, are used to define the start and end of every subarray nums[i..j]. For each such subarray, a third loop with index k is used to traverse its elements. Inside this innermost loop, we use a HashSet to keep track of the unique elements encountered. The size of the set after the loop gives the distinct count. This count is then squared and accumulated into a final sum. This process is repeated for all n * (n + 1) / 2 subarrays.

import java.util.HashSet;import java.util.Set; class Solution {    public int sumCounts(int[] nums) {        int n = nums.length;        int totalSum = 0;         for (int i = 0; i < n; i++) {            for (int j = i; j < n; j++) {                // Subarray is nums[i..j]                Set<Integer> distinctElements = new HashSet<>();                for (int k = i; k <= j; k++) {                    distinctElements.add(nums[k]);                }                int distinctCount = distinctElements.size();                totalSum += distinctCount * distinctCount;            }        }        return totalSum;    }}

Complexity

Time

O(N^3), where N is the length of `nums`. There are three nested loops. The outer two loops select a subarray (O(N^2) subarrays), and the inner loop iterates through the subarray's elements (up to O(N) elements), leading to a cubic time complexity.

Space

O(N), where N is the length of `nums`. The `HashSet` can store up to N distinct elements in the worst case for a single subarray.

Trade-offs

Pros

  • Simple to understand and implement.

  • Directly translates the problem statement into code without complex logic.

Cons

  • Highly inefficient due to its cubic time complexity.

  • Performs a lot of redundant work. For each subarray, it recalculates the distinct elements from scratch, even for overlapping subarrays.

Solutions

class Solution {public  int sumCounts(List<Integer> nums) {    int ans = 0;    int n = nums.size();    for (int i = 0; i < n; ++i) {      int[] s = new int[101];      int cnt = 0;      for (int j = i; j < n; ++j) {        if (++s[nums.get(j)] == 1) {          ++cnt;        }        ans += cnt * cnt;      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem