3321. Find X-Sum of All K-Long Subarrays II LeetCode Solution
In this guide, you will get 3321. Find X-Sum of All K-Long Subarrays II LeetCode Solution with the best time and space complexity. The solution to Find X-Sum of All K-Long Subarrays II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Find X-Sum of All K-Long Subarrays II
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.
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:
nums.length == n
1 <= n <= 105
1 <= nums[i] <= 109
1 <= x <= k <= nums.length
Complexity Analysis
Time Complexity: O(n\log n)
Space Complexity: O(n)
3321. Find X-Sum of All K-Long Subarrays II LeetCode Solution in C++
class Solution {
public:
// Same as 3318. Find X-Sum of All K-Long Subarrays I
vector<long long> findXSum(vector<int>& nums, int k, int x) {
vector<long long> ans;
long windowSum = 0;
unordered_map<int, int> count;
multiset<pair<int, int>> top; // the top x elements
multiset<pair<int, int>> bot; // the rest of the elements
// Updates the count of num by freq and the window sum accordingly.
auto update = [&count, &top, &bot, &windowSum](int num, int freq) -> void {
if (count[num] > 0) { // Clean up the old count.
if (auto it = bot.find({count[num], num}); it != bot.end()) {
bot.erase(it);
} else {
it = top.find({count[num], num});
top.erase(it);
windowSum -= static_cast<long>(num) * count[num];
}
}
count[num] += freq;
if (count[num] > 0)
bot.insert({count[num], num});
};
for (int i = 0; i < nums.size(); ++i) {
update(nums[i], 1);
if (i >= k)
update(nums[i - k], -1);
// Move the bottom elements to the top if needed.
while (!bot.empty() && top.size() < x) {
const auto [countB, b] = *bot.rbegin();
bot.erase(--bot.end());
top.insert({countB, b});
windowSum += static_cast<long>(b) * countB;
}
// Swap the bottom and top elements if needed.
while (!bot.empty() && *bot.rbegin() > *top.begin()) {
const auto [countB, b] = *bot.rbegin();
const auto [countT, t] = *top.begin();
bot.erase(--bot.end());
top.erase(top.begin());
bot.insert({countT, t});
top.insert({countB, b});
windowSum += static_cast<long>(b) * countB;
windowSum -= static_cast<long>(t) * countT;
}
if (i >= k - 1)
ans.push_back(windowSum);
}
return ans;
}
}; /* code provided by PROGIEZ */
3321. Find X-Sum of All K-Long Subarrays II LeetCode Solution in Java
class Solution {
// Same as 3318. Find X-Sum of All K-Long Subarrays I
public long[] findXSum(int[] nums, int k, int x) {
long[] ans = new long[nums.length - k + 1];
Map<Integer, Integer> count = new HashMap<>();
TreeSet<Pair<Integer, Integer>> top =
new TreeSet<>(Comparator.comparing(Pair<Integer, Integer>::getKey)
.thenComparing(Pair<Integer, Integer>::getValue));
TreeSet<Pair<Integer, Integer>> bot =
new TreeSet<>(Comparator.comparing(Pair<Integer, Integer>::getKey)
.thenComparing(Pair<Integer, Integer>::getValue));
for (int i = 0; i < nums.length; ++i) {
update(nums[i], 1, count, top, bot);
if (i >= k)
update(nums[i - k], -1, count, top, bot);
// Move the bottom elements to the top if needed.
while (!bot.isEmpty() && top.size() < x) {
Pair<Integer, Integer> pair = bot.pollLast();
top.add(pair);
windowSum += (long) pair.getValue() * pair.getKey();
}
// Swap the bottom and top elements if needed.
while (!bot.isEmpty() && (bot.last().getKey() > top.first().getKey() ||
bot.last().getKey().equals(top.first().getKey()) &&
bot.last().getValue() > top.first().getValue())) {
Pair<Integer, Integer> pairB = bot.pollLast();
Pair<Integer, Integer> pairT = top.pollFirst();
top.add(pairB);
bot.add(pairT);
windowSum += (long) pairB.getValue() * pairB.getKey();
windowSum -= (long) pairT.getValue() * pairT.getKey();
}
if (i >= k - 1)
ans[i - k + 1] = windowSum;
}
return ans;
}
private long windowSum = 0;
// Updates the count of num by freq and the window sum accordingly.
private void update(int num, int freq, Map<Integer, Integer> count,
TreeSet<Pair<Integer, Integer>> top, TreeSet<Pair<Integer, Integer>> bot) {
if (count.getOrDefault(num, 0) > 0) { // Clean up the old count.
Pair<Integer, Integer> pair = new Pair<>(count.get(num), num);
if (bot.remove(pair)) {
// Do nothing.
} else {
top.remove(pair);
windowSum -= (long) num * count.get(num);
}
}
count.merge(num, freq, Integer::sum);
if (count.get(num) > 0)
bot.add(new Pair<>(count.get(num), num));
}
} // code provided by PROGIEZ
3321. Find X-Sum of All K-Long Subarrays II LeetCode Solution in Python
from sortedcontainers import SortedList
class Solution:
# Same as 3318. Find X-Sum of All K-Long Subarrays I
def findXSum(self, nums: list[int], k: int, x: int) -> list[int]:
ans = []
windowSum = 0
count = collections.Counter()
top = SortedList() # the top x elements
bot = SortedList() # the rest of the elements
def update(num: int, freq: int) -> None:
"""Updates the count of num by freq and the window sum accordingly."""
nonlocal windowSum
if count[num] > 0: # Clean up the old count.
if [count[num], num] in bot:
bot.remove([count[num], num])
else:
top.remove([count[num], num])
windowSum -= num * count[num]
count[num] += freq
if count[num] > 0:
bot.add([count[num], num])
for i, num in enumerate(nums):
update(num, 1)
if i >= k:
update(nums[i - k], -1)
# Move the bottom elements to the top if needed.
while bot and len(top) < x:
countB, b = bot.pop()
top.add([countB, b])
windowSum += b * countB
# Swap the bottom and top elements if needed.
while bot and bot[-1] > top[0]:
countB, b = bot.pop()
countT, t = top.pop(0)
bot.add([countT, t])
top.add([countB, b])
windowSum += b * countB
windowSum -= t * countT
if i >= k - 1:
ans.append(windowSum)
return ans # code by PROGIEZ
