3318. Find X-Sum of All K-Long Subarrays I LeetCode Solution
In this guide, you will get 3318. Find X-Sum of All K-Long Subarrays I LeetCode Solution with the best time and space complexity. The solution to Find X-Sum of All K-Long Subarrays I 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 I
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:
1 <= n == nums.length <= 50
1 <= nums[i] <= 50
1 <= x <= k <= nums.length
Complexity Analysis
Time Complexity: O(n\log n)
Space Complexity: O(n)
3318. Find X-Sum of All K-Long Subarrays I LeetCode Solution in C++
class Solution {
public:
vector<int> findXSum(vector<int>& nums, int k, int x) {
vector<int> 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 -= 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 += 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 += b * countB;
windowSum -= t * countT;
}
if (i >= k - 1)
ans.push_back(windowSum);
}
return ans;
}
}; /* code provided by PROGIEZ */
3318. Find X-Sum of All K-Long Subarrays I LeetCode Solution in Java
class Solution {
public int[] findXSum(int[] nums, int k, int x) {
int[] ans = new int[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 += 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 += pairB.getValue() * pairB.getKey();
windowSum -= pairT.getValue() * pairT.getKey();
}
if (i >= k - 1)
ans[i - k + 1] = windowSum;
}
return ans;
}
private int 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 -= 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
3318. Find X-Sum of All K-Long Subarrays I LeetCode Solution in Python
from sortedcontainers import SortedList
class Solution:
def findXSum(self, nums: list[int], k: int, x: int) -> list[int]:
ans = []
windowSum = 0
count = collections.Counter()
top = SortedList()
bot = SortedList()
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 old values.
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 element 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])
windowSum -= t * countT
top.add([countB, b])
windowSum += b * countB
if i >= k - 1:
ans.append(windowSum)
return ans # code by PROGIEZ
