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

Find X-Sum of All K-Long Subarrays I

Number: 3610

Difficulty: Easy

Paid? No

Companies: Google

Problem Description

Given an array nums of n integers and two integers k and x, compute the x-sum for every contiguous subarray of length k. The x-sum is calculated by first counting the occurrence of each element in the subarray, then keeping only the occurrences for the top x most frequent elements (with ties broken by picking the larger element as more frequent), and finally summing the values (each multiplied by its count). If the subarray has less than x distinct elements, the x-sum is just the sum of the entire subarray.

Key Insights

  • Use a sliding window of size k to avoid recomputation for overlapping subarrays.
  • Maintain a frequency map (hash table) for the current window.
  • For each window, convert the frequency map into a list of tuples (frequency, value) and sort descending by frequency and value.
  • Sum the contributions (value * count) for the top x selected numbers.
  • Given constraints (n up to 50), even a sorting-based approach per window is efficient.

Space and Time Complexity

Time Complexity: O(n * (k log k)) in the worst-case, due to sorting the frequency map for each window. Space Complexity: O(n) for storing frequency counts and auxiliary lists.

Solution

We use the sliding window technique to iterate over every subarray of length k. For each window, we update a frequency map by decrementing the frequency of the element leaving the window and incrementing that of the new element entering the window. We then sort the frequency entries by frequency and then by the element value (both descending) to determine the top x elements. Finally, we compute the x-sum as the sum of the value multiplied by its frequency for these top x elements (or the entire window sum if there are less than x distinct elements).

Code Solutions

# Python Code with line-by-line comments
def find_x_sum(nums, k, x):
    n = len(nums)
    answer = []
    # frequency dictionary for the current window
    freq = {}
    
    # Initialize frequency dictionary for the first window
    for i in range(k):
        freq[nums[i]] = freq.get(nums[i], 0) + 1
    
    # Helper function to calculate x-sum given the frequency dictionary
    def calc_x_sum(freq, x):
        # If less than x distinct elements, return sum of entire window
        if len(freq) < x:
            return sum(num * count for num, count in freq.items())
        # Create list of tuples (frequency, value)
        items = [(count, num) for num, count in freq.items()]
        # Sort by frequency descending, and by value descending for tie-breakers
        items.sort(key=lambda t: (t[0], t[1]), reverse=True)
        
        # Sum the values (each multiplied by its frequency) for the top x elements
        total = 0
        for count, num in items[:x]:
            total += num * count
        return total
    
    # Calculate x-sum for the first window
    answer.append(calc_x_sum(freq, x))
    
    # Slide the window across the array
    for i in range(k, n):
        # Remove the outgoing element
        out_num = nums[i - k]
        freq[out_num] -= 1
        if freq[out_num] == 0:
            del freq[out_num]
        # Add the new incoming element
        in_num = nums[i]
        freq[in_num] = freq.get(in_num, 0) + 1
        # Append the x-sum for the current window
        answer.append(calc_x_sum(freq, x))
    
    return answer

# Example usage:
print(find_x_sum([1, 1, 2, 2, 3, 4, 2, 3], 6, 2))  # Expected Output: [6,10,12]
← Back to All Questions