We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Subarrays Distinct Element Sum of Squares I

Number: 3163

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given a 0-indexed integer array nums, the task is to find the sum of the squares of distinct counts for every contiguous non-empty subarray of nums. The "distinct count" of a subarray nums[i..j] is the number of unique elements within that subarray. For example, for nums = [1,2,1], one subarray [1,2] has 2 distinct numbers so its contribution is 2² = 4. Sum these squares over all subarrays and return the result.

Key Insights

  • The constraints (1 <= nums.length <= 100) allow for a brute force approach.
  • A nested loop structure can be used to iterate over every possible subarray.
  • Within each subarray iteration, a frequency map (or hash table) can track elements and count distinct numbers.
  • Reusing frequency counts as the subarray expands helps in updating distinct counts in O(1) time.
  • The overall time complexity is manageable (roughly O(n²)) given the small input size.

Space and Time Complexity

Time Complexity: O(n²) where n is the number of elements in nums.
Space Complexity: O(m) per subarray where m is the number of distinct elements (bounded by 100, so effectively constant).

Solution

The solution uses two nested loops to enumerate all subarrays. For each starting index, a frequency dictionary (or hash map) is maintained. As we extend the subarray by moving the ending index, we update the frequency count:

  • If an element is encountered for the first time, increment the distinct count.
  • Add the square of the current distinct count to the cumulative sum. This approach leverages a hash table to efficiently track distinct elements in each subarray.

Code Solutions

def subarraysDistinctElementSumSquares(nums):
    n = len(nums)
    total_sum = 0
    # Iterate over every possible starting index of the subarray
    for i in range(n):
        freq = {}  # Dictionary to maintain the frequency of elements in the current subarray
        distinct = 0  # Count of distinct elements in the current subarray
        # Extend the subarray from index i to the end of the list
        for j in range(i, n):
            # Update frequency for the current element
            if nums[j] in freq:
                freq[nums[j]] += 1
            else:
                freq[nums[j]] = 1
                distinct += 1  # Increment distinct count for a new element
            # Add the square of the current distinct count to the total_sum
            total_sum += distinct * distinct
    return total_sum

# Example usage:
print(subarraysDistinctElementSumSquares([1, 2, 1]))  # Expected output: 15
print(subarraysDistinctElementSumSquares([1, 1]))     # Expected output: 3
← Back to All Questions