Count Non-Decreasing Subarrays After K Operations

Challenge Points: 30

Level: Hard

You are given an integer array nums of length n and an integer k.

For each subarray of nums, you may perform up to k operations.
In each operation, you can increment any element of the subarray by 1.

Each subarray is considered independently, meaning changes in one do not affect others.

Your goal is to count the number of subarrays that can be made non-decreasing after at most k operations.

An array is said to be non-decreasing if every element is greater than or equal to the previous one.

Return the count of such subarrays.

Example 1:

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

Output: 17

Explanation:

There are a total of 21 possible subarrays. Only these 4 cannot be made non-decreasing within 7 operations: [6,3,1] [6,3,1,2] [6,3,1,2,4] [6,3,1,2,4,4] Thus, 21 - 4 = 17 subarrays can be made non-decreasing.

Example 2:

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

Output: 12

Explanation:

All subarrays of size ≤ 3 (except [6,3,1]) and the subarray [3,1,3,6] can be made non-decreasing with ≤ 4 operations. Hence, total = 12.

to Continue

Accepted:

Submission:

Report an issue

Code

You need toto run or submitYou need toto run or submit

Test Case

Test Result