1class Solution {
2    public long modeWeight(int[] nums, int k) {
3        // Map each value to its frequency within the current sliding window
4        Map<Integer, Integer> freqMap = new HashMap<>();
5
6        // Max-heap simulated with negated frequencies:
7        // entry = {-frequency, value}
8        // Ordering: higher frequency first; if frequencies tie, smaller value first
9        PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
10            (a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));
11
12        // Initialize the first window of size k
13        for (int i = 0; i < k; i++) {
14            int value = nums[i];
15            freqMap.merge(value, 1, Integer::sum);
16            // Push a snapshot of the current (frequency, value) pair
17            maxHeap.offer(new int[] {-freqMap.get(value), value});
18        }
19
20        long answer = 0;
21
22        // Lazily retrieve the mode of the current window:
23        // discard stale heap entries whose recorded frequency
24        // no longer matches the actual frequency in freqMap
25        Supplier<Long> getMode = () -> {
26            while (true) {
27                int[] top = maxHeap.peek();
28                int value = top[1];
29                int frequency = -top[0];
30                // Entry is valid only if its snapshot matches the live count
31                if (freqMap.getOrDefault(value, 0) == frequency) {
32                    return 1L * frequency * value;
33                }
34                // Stale entry: remove and keep searching
35                maxHeap.poll();
36            }
37        };
38
39        // Account for the first window
40        answer += getMode.get();
41
42        // Slide the window across the rest of the array
43        for (int i = k; i < nums.length; i++) {
44            int incoming = nums[i];      // element entering the window
45            int outgoing = nums[i - k];  // element leaving the window
46
47            // Add the incoming element and push its updated snapshot
48            freqMap.merge(incoming, 1, Integer::sum);
49            maxHeap.offer(new int[] {-freqMap.get(incoming), incoming});
50
51            // Remove the outgoing element and push its updated snapshot
52            freqMap.merge(outgoing, -1, Integer::sum);
53            maxHeap.offer(new int[] {-freqMap.get(outgoing), outgoing});
54
55            // Accumulate the mode weight of the current window
56            answer += getMode.get();
57        }
58
59        return answer;
60    }
61}
62

1class Solution {
2public:
3    long long modeWeight(vector<int>& nums, int k) {
4        // freq_count[v] = current frequency of value v inside the sliding window
5        unordered_map<int, int> freq_count;
6
7        // Max-heap storing {frequency, -value}.
8        // - Ordered by frequency first (higher frequency on top).
9        // - Negated value as tie-breaker, so the SMALLER value wins
10        //   when two values share the same frequency.
11        // Stale entries are allowed and removed lazily.
12        priority_queue<pair<int, int>> max_heap;
13
14        // ---------- Step 1: Build the first window of size k ----------
15        for (int i = 0; i < k; i++) {
16            int val = nums[i];
17            freq_count[val]++;
18            max_heap.push({freq_count[val], -val});
19        }
20
21        // ---------- Step 2: Helper to fetch the current mode's weight ----------
22        // Lazy deletion: pop entries whose stored frequency no longer matches
23        // the real frequency in freq_count (i.e., outdated snapshots).
24        auto get_mode = [&]() -> long long {
25            while (true) {
26                auto [freq, neg_val] = max_heap.top();
27                int val = -neg_val;
28                if (freq_count[val] == freq) {
29                    // Valid entry: this is the true mode of the window.
30                    // Weight = frequency * value.
31                    return 1LL * freq * val;
32                }
33                // Outdated entry, discard it.
34                max_heap.pop();
35            }
36        };
37
38        long long ans = 0;
39        ans += get_mode(); // mode weight of the initial window
40
41        // ---------- Step 3: Slide the window across the array ----------
42        for (int i = k; i < (int)nums.size(); i++) {
43            int in_val = nums[i];       // element entering the window
44            int out_val = nums[i - k];  // element leaving the window
45
46            // Update frequencies for both elements.
47            freq_count[in_val]++;
48            freq_count[out_val]--;
49
50            // Push fresh snapshots; old snapshots become stale and
51            // will be cleaned up lazily inside get_mode().
52            max_heap.push({freq_count[in_val], -in_val});
53            max_heap.push({freq_count[out_val], -out_val});
54
55            // Accumulate the mode weight of the current window.
56            ans += get_mode();
57        }
58
59        return ans;
60    }
61};
62

1// ---------- Min/Max Heap Implementation ----------
2// A generic binary heap ordered by a custom comparator.
3// comparator(a, b) < 0 means `a` has higher priority than `b`.
4
5type HeapEntry = [number, number]; // [frequency, value]
6
7const heap: HeapEntry[] = [];
8
9// Comparator for the max-heap:
10// - Higher frequency comes first.
11// - On equal frequency, the SMALLER value wins (tie-breaker).
12function compare(a: HeapEntry, b: HeapEntry): number {
13    if (a[0] !== b[0]) return b[0] - a[0]; // larger frequency first
14    return a[1] - b[1];                    // smaller value first
15}
16
17// Insert an entry and restore heap order by sifting it up.
18function heapPush(entry: HeapEntry): void {
19    heap.push(entry);
20    let idx = heap.length - 1;
21    while (idx > 0) {
22        const parent = (idx - 1) >> 1;
23        if (compare(heap[idx], heap[parent]) < 0) {
24            [heap[idx], heap[parent]] = [heap[parent], heap[idx]];
25            idx = parent;
26        } else {
27            break;
28        }
29    }
30}
31
32// Return the highest-priority entry without removing it.
33function heapTop(): HeapEntry {
34    return heap[0];
35}
36
37// Remove the highest-priority entry and restore heap order by sifting down.
38function heapPop(): void {
39    const last = heap.pop()!;
40    if (heap.length === 0) return;
41    heap[0] = last;
42    let idx = 0;
43    const n = heap.length;
44    while (true) {
45        const left = idx * 2 + 1;
46        const right = idx * 2 + 2;
47        let best = idx;
48        if (left < n && compare(heap[left], heap[best]) < 0) best = left;
49        if (right < n && compare(heap[right], heap[best]) < 0) best = right;
50        if (best === idx) break;
51        [heap[idx], heap[best]] = [heap[best], heap[idx]];
52        idx = best;
53    }
54}
55
56// ---------- Main Function ----------
57function modeWeight(nums: number[], k: number): number {
58    // Reset global heap state for repeated calls.
59    heap.length = 0;
60
61    // freqCount.get(v) = current frequency of value v inside the sliding window.
62    const freqCount: Map<number, number> = new Map();
63
64    // ---------- Step 1: Build the first window of size k ----------
65    for (let i = 0; i < k; i++) {
66        const val = nums[i];
67        freqCount.set(val, (freqCount.get(val) ?? 0) + 1);
68        // Push a fresh snapshot of (frequency, value).
69        heapPush([freqCount.get(val)!, val]);
70    }
71
72    // ---------- Step 2: Helper to fetch the current mode's weight ----------
73    // Lazy deletion: pop entries whose stored frequency no longer matches
74    // the real frequency in freqCount (i.e., outdated snapshots).
75    const getMode = (): number => {
76        while (true) {
77            const [freq, val] = heapTop();
78            if (freqCount.get(val) === freq) {
79                // Valid entry: this is the true mode of the window.
80                // Weight = frequency * value.
81                return freq * val;
82            }
83            // Outdated entry, discard it.
84            heapPop();
85        }
86    };
87
88    let ans = 0;
89    ans += getMode(); // mode weight of the initial window
90
91    // ---------- Step 3: Slide the window across the array ----------
92    for (let i = k; i < nums.length; i++) {
93        const inVal = nums[i];      // element entering the window
94        const outVal = nums[i - k]; // element leaving the window
95
96        // Update frequencies for both elements.
97        freqCount.set(inVal, (freqCount.get(inVal) ?? 0) + 1);
98        freqCount.set(outVal, (freqCount.get(outVal) ?? 0) - 1);
99
100        // Push fresh snapshots; old snapshots become stale and
101        // will be cleaned up lazily inside getMode().
102        heapPush([freqCount.get(inVal)!, inVal]);
103        heapPush([freqCount.get(outVal)!, outVal]);
104
105        // Accumulate the mode weight of the current window.
106        ans += getMode();
107    }
108
109    return ans;
110}
111