3420. Count Non-Decreasing Subarrays After K Operations LeetCode Solution
In this guide, you will get 3420. Count Non-Decreasing Subarrays After K Operations LeetCode Solution with the best time and space complexity. The solution to Count Non-Decreasing Subarrays After K Operations problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Count Non-Decreasing Subarrays After K Operations
You are given an array nums of n integers and an integer k.
For each subarray of nums, you can apply up to k operations on it. In each operation, you increment any element of the subarray by 1.
Note that each subarray is considered independently, meaning changes made to one subarray do not persist to another.
Return the number of subarrays that you can make non-decreasing after performing at most k operations.
An array is said to be non-decreasing if each element is greater than or equal to its previous element, if it exists.
Example 1:
Input: nums = [6,3,1,2,4,4], k = 7
Output: 17
Explanation:
Out of all 21 possible subarrays of nums, only the subarrays [6, 3, 1], [6, 3, 1, 2], [6, 3, 1, 2, 4] and [6, 3, 1, 2, 4, 4] cannot be made non-decreasing after applying up to k = 7 operations. Thus, the number of non-decreasing subarrays is 21 – 4 = 17.
Input: nums = [6,3,1,3,6], k = 4
Output: 12
Explanation:
The subarray [3, 1, 3, 6] along with all subarrays of nums with three or fewer elements, except [6, 3, 1], can be made non-decreasing after k operations. There are 5 subarrays of a single element, 4 subarrays of two elements, and 2 subarrays of three elements except [6, 3, 1], so there are 1 + 5 + 4 + 2 = 12 subarrays that can be made non-decreasing.
3420. Count Non-Decreasing Subarrays After K Operations LeetCode Solution in C++
class Solution {
public:
long long countNonDecreasingSubarrays(vector<int>& nums, int k) {
long ans = 0;
long cost = 0;
// Store (number, count) pairs in non-increasing order. The numbers in the
// queue represent what nums[i..j] look like after adjustments.
deque<pair<int, int>> dq;
for (int i = nums.size() - 1, j = nums.size() - 1; i >= 0; --i) {
const int num = nums[i];
int count = 1;
while (!dq.empty() && dq.back().first < num) {
const auto [nextNum, nextCount] = dq.back();
dq.pop_back();
count += nextCount;
// Adjust `nextNum`s to `num`.
cost += static_cast<long>(num - nextNum) * nextCount;
}
dq.emplace_back(num, count);
while (cost > k) {
const auto [rightmostNum, rightmostCount] = dq.front();
dq.pop_front();
cost -= static_cast<long>(rightmostNum - nums[j--]);
if (rightmostCount > 1)
dq.emplace_front(rightmostNum, rightmostCount - 1);
}
ans += j - i + 1;
}
return ans;
}
}; /* code provided by PROGIEZ */
3420. Count Non-Decreasing Subarrays After K Operations LeetCode Solution in Java
class Solution {
public long countNonDecreasingSubarrays(int[] nums, int k) {
long ans = 0;
long cost = 0;
// Store (number, count) pairs in non-increasing order. The numbers in the
// queue represent what nums[i..j] look like after adjustments.
Deque<Pair<Integer, Integer>> dq = new ArrayDeque<>();
for (int i = nums.length - 1, j = nums.length - 1; i >= 0; --i) {
final int num = nums[i];
int count = 1;
while (!dq.isEmpty() && dq.getLast().getKey() < num) {
final int nextNum = dq.getLast().getKey();
final int nextCount = dq.removeLast().getValue();
count += nextCount;
// Adjust `nextNum`s to `num`.
cost += (long) (num - nextNum) * nextCount;
}
dq.offerLast(new Pair<>(num, count));
while (cost > k) {
final int rightmostNum = dq.getFirst().getKey();
final int rightmostCount = dq.removeFirst().getValue();
cost -= (long) (rightmostNum - nums[j--]);
if (rightmostCount > 1)
dq.offerFirst(new Pair<>(rightmostNum, rightmostCount - 1));
}
ans += j - i + 1;
}
return ans;
}
} // code provided by PROGIEZ
3420. Count Non-Decreasing Subarrays After K Operations LeetCode Solution in Python
class Solution:
def countNonDecreasingSubarrays(self, nums: list[int], k: int) -> int:
ans = 0
cost = 0
# Store (number, count) pairs in non-increasing order. The numbers in the
# queue represent what nums[i..j] look like after adjustments.
dq = collections.deque()
j = len(nums) - 1
for i, num in reversed(list(enumerate(nums))):
count = 1
while dq and dq[-1][0] < num:
nextNum, nextCount = dq.pop()
count += nextCount
cost += (num - nextNum) * nextCount # Adjust `nextNum`s to `num`.
dq.append((num, count))
while cost > k: # Remove the rightmost number.
rightmostNum, rightmostCount = dq.popleft()
cost -= (rightmostNum - nums[j])
j -= 1
if rightmostCount > 1:
dq.appendleft((rightmostNum, rightmostCount - 1))
ans += j - i + 1
return ans # code by PROGIEZ
