Nitin Ahirwal | Engineer, Developer & Tech Enthusiast

Hey folks 👋

This is Day 51 of my LeetCode streak 🚀 Today’s problem is 3321. Find X-Sum of All K-Long Subarrays II — a hard-level extension of the previous day’s problem, demanding a more optimized approach using heaps and lazy updates for large input sizes (n ≤ 10⁵).

📌 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:

Counting the occurrences of all elements.
Keeping only the top x most frequent elements.
- If two elements have the same frequency, the element with the larger value is preferred.
Calculating the sum of all kept elements.

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].

💡 Intuition

The naive approach of recalculating frequencies for every subarray of size k leads to O(n × k) complexity — infeasible for large n. Instead, we can use a sliding window + frequency map to incrementally maintain element counts and determine which elements belong to the top X.

However, the challenge lies in efficiently knowing which elements are currently the top X frequent elements as counts change dynamically when the window slides.

To solve this, we maintain two heaps:

Best heap → contains the top X elements (by frequency and value).
Rest heap → contains the remaining elements. We also use lazy deletion (version tracking) to handle outdated heap entries.

🔑 Approach

Sliding Window with Frequency Map: Use a Map to store the frequency of each element in the current window.
Two Heaps (Balanced Priority Queues):
- best: a min-heap of selected top X elements (worst among the best at the top).
- rest: a max-heap of the remaining elements (best among the rest at the top).
- Comparator ensures order by frequency (desc), then value (desc).
Lazy Deletion: Each element’s heap entry includes a version number. When frequency changes, increment the version. Stale entries are ignored when encountered at the top of the heap.
Dynamic Rebalancing:
- Maintain best.size() ≤ X.
- If a better element exists in rest, swap it with the worst in best.
- Track a running sum sumBest representing the total contribution from elements in best.
Window Update Operations:
- When an element enters: increment its count and update heap membership.
- When an element exits: decrement its count or remove it if zero.
- After each change, rebalance heaps and record the current sumBest.
Edge Case: If k === x, all elements are always part of the top X; use a simple sliding window sum.

⏱️ Complexity Analysis

Time Complexity: Each element is added and removed once, and each heap operation takes O(log D) where D = number of distinct elements in the window. → Overall: ( O(n \log D) )
Space Complexity: Heaps and frequency maps store at most D elements. → Overall: ( O(D) )

🧑‍💻 Code (JavaScript)

/**
 * @param {number[]} nums
 * @param {number} k
 * @param {number} x
 * @return {number[]}
 */
var findXSum = function(nums, k, x) {
  const n = nums.length;
  if (k === x) { // shortcut: keep all elements
    const ans = [];
    let win = 0;
    for (let i = 0; i < k; i++) win += nums[i];
    ans.push(win);
    for (let i = k; i < n; i++) {
      win += nums[i] - nums[i - k];
      ans.push(win);
    }
    return ans;
  }

  class Heap {
    constructor(cmp) { this.a = []; this.cmp = cmp; }
    size() { return this.a.length; }
    peek() { return this.a[0]; }
    push(v) { this.a.push(v); this._up(this.a.length - 1); }
    pop() {
      const a = this.a;
      const top = a[0];
      const last = a.pop();
      if (a.length) { a[0] = last; this._down(0); }
      return top;
    }
    _up(i) {
      const a = this.a, cmp = this.cmp;
      while (i > 0) {
        const p = (i - 1) >> 1;
        if (!cmp(a[i], a[p])) break;
        [a[i], a[p]] = [a[p], a[i]];
        i = p;
      }
    }
    _down(i) {
      const a = this.a, cmp = this.cmp;
      while (true) {
        let l = i * 2 + 1, r = l + 1, best = i;
        if (l < a.length && cmp(a[l], a[best])) best = l;
        if (r < a.length && cmp(a[r], a[best])) best = r;
        if (best === i) break;
        [a[i], a[best]] = [a[best], a[i]];
        i = best;
      }
    }
  }

  const cmpBest = (e1, e2) => e1.freq !== e2.freq ? e1.freq < e2.freq : e1.val < e2.val;
  const cmpRest = (e1, e2) => e1.freq !== e2.freq ? e1.freq > e2.freq : e1.val > e2.val;

  const best = new Heap(cmpBest), rest = new Heap(cmpRest);
  const cnt = new Map(), inBest = new Map(), ver = new Map();

  let bestCount = 0, sumBest = 0n;
  const big = (x) => BigInt(x);

  const getVer = (v) => ver.get(v) || 0;
  const bumpVer = (v) => ver.set(v, getVer(v) + 1);
  const getCnt = (v) => cnt.get(v) || 0;
  const setCnt = (v, c) => c === 0 ? cnt.delete(v) : cnt.set(v, c);
  const isInBest = (v) => inBest.get(v) === true;
  const setInBest = (v, b) => inBest.set(v, b);

  const cleanTop = (heap, check) => {
    while (heap.size()) {
      const t = heap.peek();
      if (check(t)) { heap.pop(); continue; }
      break;
    }
  };

  const pushToProperHeap = (v) => {
    const f = getCnt(v); if (f === 0) return;
    const stamp = getVer(v);
    const node = { val: v, freq: f, stamp };
    (isInBest(v) ? best : rest).push(node);
  };

  const promoteFromRest = () => {
    cleanTop(rest, (t) => getVer(t.val) !== t.stamp || isInBest(t.val) || getCnt(t.val) !== t.freq);
    if (!rest.size()) return false;
    const t = rest.pop();
    setInBest(t.val, true);
    bestCount++;
    sumBest += big(getCnt(t.val)) * big(t.val);
    pushToProperHeap(t.val);
    return true;
  };

  const demoteFromBest = () => {
    cleanTop(best, (t) => getVer(t.val) !== t.stamp || !isInBest(t.val) || getCnt(t.val) !== t.freq);
    if (!best.size()) return false;
    const t = best.pop();
    setInBest(t.val, false);
    bestCount--;
    sumBest -= big(getCnt(t.val)) * big(t.val);
    pushToProperHeap(t.val);
    return true;
  };

  const rebalance = () => {
    while (bestCount < x) if (!promoteFromRest()) break;
    while (bestCount > x) demoteFromBest();
    while (true) {
      cleanTop(best, (t) => getVer(t.val) !== t.stamp || !isInBest(t.val) || getCnt(t.val) !== t.freq);
      cleanTop(rest, (t) => getVer(t.val) !== t.stamp || isInBest(t.val) || getCnt(t.val) !== t.freq);
      if (!best.size() || !rest.size()) break;
      const worstBest = best.peek(), bestRest = rest.peek();
      const better = (bestRest.freq > worstBest.freq) || (bestRest.freq === worstBest.freq && bestRest.val > worstBest.val);
      if (!better) break;
      best.pop(); rest.pop();
      setInBest(worstBest.val, false); sumBest -= big(getCnt(worstBest.val)) * big(worstBest.val);
      setInBest(bestRest.val, true); sumBest += big(getCnt(bestRest.val)) * big(bestRest.val);
      pushToProperHeap(worstBest.val); pushToProperHeap(bestRest.val);
    }
  };

  const add = (v) => {
    const old = getCnt(v), neu = old + 1;
    setCnt(v, neu); bumpVer(v);
    if (isInBest(v)) sumBest += big(v);
    if (!inBest.has(v)) setInBest(v, false);
    pushToProperHeap(v);
    rebalance();
  };

  const remove = (v) => {
    const old = getCnt(v), neu = old - 1;
    bumpVer(v);
    if (isInBest(v)) sumBest -= big(v);
    if (neu === 0) {
      setCnt(v, 0);
      if (isInBest(v)) { setInBest(v, false); bestCount--; }
    } else setCnt(v, neu);
    pushToProperHeap(v);
    rebalance();
  };

  const ans = [];
  for (let i = 0; i < k; i++) add(nums[i]);
  rebalance(); ans.push(Number(sumBest));
  for (let i = k; i < n; i++) { add(nums[i]); remove(nums[i - k]); ans.push(Number(sumBest)); }
  return ans;
};

🧪 Example

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

Output: [6, 10, 12]

Explanation:

[1,1,2,2,3,4] → top 2: (1, 2) → sum = 6
[1,2,2,3,4,2] → top 2: (2, 4) → sum = 10
[2,2,3,4,2,3] → top 2: (2, 3) → sum = 12

🎯 Reflection

This problem elegantly demonstrates the power of combining priority queues and lazy updates to efficiently maintain dynamic ranking under frequent updates. Though complex, this approach scales well and generalizes to many “top-K dynamic frequency” scenarios.

That’s it for Day 51 of my LeetCode journey 💪 Let’s keep pushing boundaries — consistency beats intensity! 🚀

Happy Coding 👨‍💻