Scale Engineer

Subarrays Distinct Element Sum of Squares II

Hard
#2597Time: O(n³) - There are three nested loops. The outer two loops iterate through all O(n²) subarrays, and for each subarray of average length O(n), we iterate through its elements. This results in a cubic time complexity.Space: O(n) - In the worst-case scenario, a subarray can contain `n` distinct elements, requiring the `HashSet` to store up to `n` items.
Patterns
Dynamic Programming
Data structures
ArrayBinary Indexed TreeSegment Tree

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.

Since the answer may be very large, return it modulo 109 + 7.

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 = [2,2]
Output: 3
Explanation: Three possible subarrays are:
[2]: 1 distinct value
[2]: 1 distinct value
[2,2]: 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 <= 105
  • 1 <= nums[i] <= 105

Approaches

3 approaches with complexity analysis and trade-offs.

This is the most straightforward and naive approach. It involves generating every possible subarray, and for each subarray, counting the number of distinct elements. The square of this count is then added to a running total. This method is easy to conceptualize but highly inefficient.

Algorithm

  • Initialize total_sum to 0.
  • Iterate through all possible start indices i from 0 to n-1.
  • Iterate through all possible end indices j from i to n-1.
    • This defines a subarray nums[i..j].
    • Create a new HashSet to store elements of this subarray.
    • Iterate from k = i to j and add nums[k] to the HashSet.
    • Get the size of the HashSet, which is the distinct count d.
    • Add d*d to total_sum, taking modulo 10^9 + 7.
  • Return total_sum.

Walkthrough

The brute-force approach uses three nested loops to solve the problem. The outer two loops, with indices i and j, are used to define the start and end of every possible subarray nums[i..j]. For each of these subarrays, a third loop iterates from i to j. Inside this innermost loop, we use a HashSet to keep track of the unique elements encountered within the current subarray. After the inner loop completes, the size of the HashSet gives us the distinct count, d. We then compute d*d and add it to our total sum. To prevent integer overflow, all additions to the sum are performed modulo 10^9 + 7.

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

Complexity

Time

O(n³) - There are three nested loops. The outer two loops iterate through all O(n²) subarrays, and for each subarray of average length O(n), we iterate through its elements. This results in a cubic time complexity.

Space

O(n) - In the worst-case scenario, a subarray can contain `n` distinct elements, requiring the `HashSet` to store up to `n` items.

Trade-offs

Pros

  • Simple to understand and implement.

  • Correct for small input sizes.

Cons

  • Extremely inefficient due to its cubic time complexity.

  • Will result in a 'Time Limit Exceeded' error for the given constraints.

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