LeetCode Challenge Day 50 — 3318. Find X-Sum of All K-Long Subarrays I

Hey folks 👋

This is Day 50 of my LeetCode streak 🚀
Today’s problem is 3318. Find X-Sum of All K-Long Subarrays I — an easy-level problem that blends frequency counting and sorting to determine the “X-sum” for each subarray.

📌 Problem Statement

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

The x-sum of an array is calculated by:

1. Counting the occurrences of all elements.
2. Keeping only the top x most frequent elements (if tied, larger values are considered more frequent).
3. Summing all the remaining elements after filtering.

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

💡 Intuition

The task is to compute an x-sum for every subarray of size k.
Since both n and the element values are small (≤ 50), we can efficiently use a frequency array to maintain counts within a sliding window.

Each time the window moves, we update the counts for incoming and outgoing elements and compute the x-sum using the top x frequent elements.

🔑 Approach

1. Maintain a frequency array cnt[51] since nums[i] ∈ [1..50].
2. Initialize it for the first window of length k.
3. For each window:
   • Build a list of [count, value] pairs for all elements with nonzero count.
   • Sort the list by:
     • Count (descending)
     • Value (descending)
   • Take the top x pairs and compute sum += count * value.
4. Slide the window:
   • Decrease count of the element leaving.
   • Increase count of the element entering.
   • Recompute the x-sum.
5. Store results in an output array and return.

⏱️ Complexity Analysis

• Time complexity:
  ( O(n \times 50 \log 50) ) ≈ O(n) (since constants are small).

• Space complexity:
  ( O(50) ) = O(1) — only a fixed-size frequency array and temporary list are used.

🧑‍💻 Code (JavaScript)

/**
 * @param {number[]} nums
 * @param {number} k
 * @param {number} x
 * @return {number[]}
 */
var findXSum = function(nums, k, x) {
  const n = nums.length;
  const res = [];
  const cnt = Array(51).fill(0); // nums[i] ∈ [1..50]

  // initialize first window
  for (let i = 0; i < k; i++) cnt[nums[i]]++;

  const computeXSum = () => {
    const present = [];
    for (let v = 1; v <= 50; v++) {
      if (cnt[v] > 0) present.push([cnt[v], v]); // [count, value]
    }
    // sort by count desc, then value desc
    present.sort((a, b) => (b[0] - a[0]) || (b[1] - a[1]));

    let sum = 0;
    for (let i = 0; i < Math.min(x, present.length); i++) {
      const [c, v] = present[i];
      sum += c * v; // keep all occurrences of chosen values
    }
    return sum;
  };

  res.push(computeXSum());

  // slide the window
  for (let i = k; i < n; i++) {
    cnt[nums[i - k]]--;
    cnt[nums[i]]++;
    res.push(computeXSum());
  }

  return res;
};

🧪 Example Walkthrough

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

Output: [6, 10, 12]

Explanation:

Subarray [1,1,2,2,3,4] → keep top 2 (1, 2) → sum = 1+1+2+2 = 6

Subarray [1,2,2,3,4,2] → keep top 2 (2, 4) → sum = 2+2+2+4 = 10

Subarray [2,2,3,4,2,3] → keep top 2 (2, 3) → sum = 2+2+2+3+3 = 12

🎯 Reflection

This problem highlights how frequency-based filtering and window management can simplify complex conditions. The constraints allow for an elegant and readable brute-force approach that’s still efficient in practice.

That’s it for Day 50 of my LeetCode journey 💪 Let’s keep the momentum going — consistency compounds! 🚀

Happy Coding 👨‍💻