3420. Count Non-Decreasing Subarrays After K Operations

/**
 * Problem: LeetCode 3420 - Count Non-Decreasing Subarrays After K Operations
 * Difficulty: Hard
 * Language: Java
 * Author: CodeByTushu
 */
import java.util.ArrayDeque;

class Solution {
    public long countNonDecreasingSubarrays(int[] nums, int k) {
        int n = nums.length;
        long[] pre = new long[n + 1];
        for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];

        // Deque maintains indices of prefix max steps (front = left side)
        ArrayDeque<Integer> dq = new ArrayDeque<>();
        long total = 0; // window [l..r] sum of prefixMax
        int r = n - 1;
        long ans = 0;

        for (int l = n - 1; l >= 0; l--) {
            // Add nums[l] to the left, remove smaller/equal records
            while (!dq.isEmpty() && nums[dq.peekFirst()] <= nums[l]) {
                int f = dq.pollFirst();
                int end = dq.isEmpty() ? r + 1 : dq.peekFirst();
                total -= (long) nums[f] * (end - f);
            }
            int end = dq.isEmpty() ? r + 1 : dq.peekFirst();
            total += (long) nums[l] * (end - l);
            dq.offerFirst(l);

            // cost = sum(prefixMax) - sum(nums) in window [l..r]
            long cost = total - (pre[r + 1] - pre[l]);

            // If cost > k, shrink window from right side
            while (cost > k) {
                int last = dq.peekLast();
                total -= nums[last];
                if (last == r) dq.pollLast();
                r--;
                cost = total - (pre[r + 1] - pre[l]);
            }

            ans += (long) (r - l + 1);
        }

        return ans;
    }
}

"""
Problem: LeetCode 3420 - Count Non-Decreasing Subarrays After K Operations
Difficulty: Hard
Language: Python 3
Author: CodeByTushu
"""

from collections import deque
from typing import List


class Solution:
    def countNonDecreasingSubarrays(self, nums: List[int], k: int) -> int:
        n = len(nums)
        pre = [0] * (n + 1)
        for i in range(n):
            pre[i + 1] = pre[i] + nums[i]

        dq = deque()  # stores indices of prefix max steps (front = left side)
        total = 0     # sum of prefixMax in window [l..r]
        r = n - 1
        ans = 0

        for l in range(n - 1, -1, -1):
            # Add nums[l] to the left, pop smaller/equal records
            while dq and nums[dq[0]] <= nums[l]:
                f = dq.popleft()
                end = dq[0] if dq else r + 1
                total -= nums[f] * (end - f)

            end = dq[0] if dq else r + 1
            total += nums[l] * (end - l)
            dq.appendleft(l)

            # cost = sum(prefixMax) - sum(nums) in window [l..r]
            cost = total - (pre[r + 1] - pre[l])

            # If cost > k, shrink window from right side
            while cost > k:
                last = dq[-1]
                total -= nums[last]
                if last == r:
                    dq.pop()
                r -= 1
                cost = total - (pre[r + 1] - pre[l])

            ans += r - l + 1

        return ans

/**
 * Problem: LeetCode 3420 - Count Non-Decreasing Subarrays After K Operations
 * Difficulty: Hard
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <deque>

class Solution {
public:
    long long countNonDecreasingSubarrays(std::vector<int>& nums, int k) {
        int n = static_cast<int>(nums.size());
        std::vector<long long> pre(n + 1, 0);
        for (int i = 0; i < n; ++i) {
            pre[i + 1] = pre[i] + nums[i];
        }

        std::deque<int> dq; // front = left side
        long long total = 0;
        int r = n - 1;
        long long ans = 0;

        for (int l = n - 1; l >= 0; --l) {
            // Add nums[l] to the left, pop smaller/equal records
            while (!dq.empty() && nums[dq.front()] <= nums[l]) {
                int f = dq.front();
                dq.pop_front();
                int end = dq.empty() ? r + 1 : dq.front();
                total -= static_cast<long long>(nums[f]) * (end - f);
            }
            int end = dq.empty() ? r + 1 : dq.front();
            total += static_cast<long long>(nums[l]) * (end - l);
            dq.push_front(l);

            // cost = sum(prefixMax) - sum(nums) in window [l..r]
            long long cost = total - (pre[r + 1] - pre[l]);

            // If cost > k, shrink window from right side
            while (cost > k) {
                int last = dq.back();
                total -= nums[last];
                if (last == r) {
                    dq.pop_back();
                }
                --r;
                cost = total - (pre[r + 1] - pre[l]);
            }

            ans += (r - l + 1);
        }

        return ans;
    }
};

/**
 * Problem: LeetCode 3420 - Count Non-Decreasing Subarrays After K Operations
 * Difficulty: Hard
 * Language: JavaScript
 * Author: CodeByTushu
 */

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var countNonDecreasingSubarrays = function(nums, k) {
    const n = nums.length;
    const pre = new Float64Array(n + 1);
    for (let i = 0; i < n; i++) {
        pre[i + 1] = pre[i] + nums[i];
    }

    // High performance array-backed deque (front push/pop and back pop)
    const buf = new Int32Array(n + 10);
    let head = n + 5;
    let tail = n + 5;

    let total = 0;
    let r = n - 1;
    let ans = 0;

    for (let l = n - 1; l >= 0; l--) {
        // Add nums[l] to the left, remove smaller/equal records
        while (head < tail && nums[buf[head]] <= nums[l]) {
            const f = buf[head++];
            const end = (head < tail) ? buf[head] : r + 1;
            total -= nums[f] * (end - f);
        }

        const end = (head < tail) ? buf[head] : r + 1;
        total += nums[l] * (end - l);
        buf[--head] = l;

        // cost = sum(prefixMax) - sum(nums) in window [l..r]
        let cost = total - (pre[r + 1] - pre[l]);

        // If cost exceeds k, shrink window from right side
        while (cost > k) {
            const last = buf[tail - 1];
            total -= nums[last];
            if (last === r) {
                tail--;
            }
            r--;
            cost = total - (pre[r + 1] - pre[l]);
        }

        ans += (r - l + 1);
    }

    return ans;
};