3318.Find_X-Sum_of_All_K-Long_Subarrays_I(Easy).md

3318. Find X-Sum of All K-Long Subarrays I (Easy)

Date and Time: Oct 16, 2024, 20:43 (EST)

Link: https://leetcode.com/problems/find-x-sum-of-all-k-long-subarrays-i/

Question:

You are given an array nums of n integers and two integers k and x.

The x-sum of an array is calculated by the following procedure:

• Count the occurrences of all elements in the array.

• Keep only the occurrences of the top x most frequent elements. If two elements have the same number of occurrences, the element with the bigger value is considered more frequent.

• Calculate the sum of the resulting array.

Note that if an array has less than x distinct elements, its x-sum is the sum of the array.

Return an integer array answer of length n - k + 1 where answer[i] is the x-sum of the subarray nums[i..i + k - 1].

Example 1:

Input: nums = [1,1,2,2,3,4,2,3], k = 6, x = 2

Output: [6,10,12]

Explanation:

• For subarray [1, 1, 2, 2, 3, 4], only elements 1 and 2 will be kept in the resulting array. Hence, answer[0] = 1 + 1 + 2 + 2.
• For subarray [1, 2, 2, 3, 4, 2], only elements 2 and 4 will be kept in the resulting array. Hence, answer[1] = 2 + 2 + 2 + 4. Note that 4 is kept in the array since it is bigger than 3 and 1 which occur the same number of times.
• For subarray [2, 2, 3, 4, 2, 3], only elements 2 and 3 are kept in the resulting array. Hence, answer[2] = 2 + 2 + 2 + 3 + 3.

Example 2:

Input: nums = [3,8,7,8,7,5], k = 2, x = 2

Output: [11,15,15,15,12]

Explanation:
Since k == x, answer[i] is equal to the sum of the subarray nums[i..i + k - 1].

Constraints:

• 1 <= n == nums.length <= 50

• 1 <= nums[i] <= 50

• 1 <= x <= k <= nums.length

Walk-through:

1. Maintain a hashmap{} to keep the occurences of elements within current length k sliding window.

2. Follow the hint to create a x_sum() function and pass in hashmap{} to calculate the x-sum. In the x_sum() function, we use maxHeap[] to keep track of the top x frequent elements, and the way we sort maxHeap[] is by counts and keys ([-val, -key]), so we ensure the most frequent elements sort in top, and breaking tie by the value of bigger element.

3. Each time we call x_sum() and append the result into the res[]. And we update the hashmap by first removing the prev sliding window's left-most element, then adding the new element into hashmap[].

Python Brute Force:

class Solution:
    def findXSum(self, nums: List[int], k: int, x: int) -> List[int]:
        # To form an arrary with length n-k+1
        # For each answer[i], find subarray with length k, x-sum
        # x-sum: the top x frequent elements sum
        # Sliding window with length k, each time we maintain the x-sum with a hashmap, hashmap contains all elements occurences

        # TC: O(n^2), SC: O(n^2)
        res = []
        n = len(nums)
        hashmap = {}    # Save elements with occurences

        # X-sum func, input: arrary, output: sum
        def x_sum(arr):
            hashmap = {}
            maxHeap = []    # Get the top x elements from here
            res = 0
            for i in arr:
                hashmap[i] = hashmap.get(i, 0) + 1
            for key, val in hashmap.items():
                heapq.heappush(maxHeap, [-val, -key])
            for _ in range(x):
                if maxHeap:
                    val, key = heapq.heappop(maxHeap)
                    res += val * key
            return res
        
        # Maintain a sliding window with size k
        for i in range(n-k+1):
            res.append(x_sum(nums[i:i+k]))
        return res

Time Complexity: $O(n^2)$
Space Complexity: $O(n^2)$

Python Optimized Solution:

class Solution:
    def findXSum(self, nums: List[int], k: int, x: int) -> List[int]:
        # Maintain hashmap and pass in x_sum()

        # TC: O(nlogk), SC: O(k)
        res = []
        n = len(nums)
        hashmap = Counter(nums[:k])

        # X-sum func, input: arrary, output: sum
        def x_sum(hashmap):
            maxHeap = []    # Get the top x elements from here
            res = 0
            for key, val in hashmap.items():
                heapq.heappush(maxHeap, [-val, -key])
            for _ in range(min(len(maxHeap), x)):
                val, key = heapq.heappop(maxHeap)
                res += val * key
            return res
        
        # Run the first time for nums[:k]
        res.append(x_sum(hashmap))
        # Maintain a sliding window with size k
        for i in range(1, n-k+1):
            # Remove the leftmost prev sliding window element
            hashmap[nums[i-1]] -= 1
            if hashmap[nums[i-1]] == 0:
                del hashmap[nums[i-1]]
            # Add the next element into hashmap
            hashmap[nums[i+k-1]] = hashmap.get(nums[i+k-1], 0) + 1
            # Pass the updated hashmap into x_sum()
            res.append(x_sum(hashmap))
        return res

Time Complexity: $O(nlog\ k)$, n is length of nums, k is just k (how many elements within sliding window). Because we loop over nums for $O(n)$, and we involve heapq.heappush(), heapq.heappop() for every iteration, which takes $O(log\ k)$ each, so the overall time complexity is $O(n*log\ k)$.
Space Complexity: $O(k)$, we only store k elements in maxHeap.