LeetCode 3420 | Count Non-Decreasing Subarrays After K Ops | Java | Hard | Deque | CodeByTushu
Description: π Welcome Back to CodeByTushu!
In todayβs video, we solve LeetCode 3420 β Count Non-Decreasing Subarrays After K Operations using Monotonic Deque and Sliding Window in Java.
We are given an integer array nums and an integer k. For any contiguous subarray, we can increment elements up to k times. We need to determine how many subarrays can be transformed into non-decreasing order without exceeding this operation budget. To make a subarray non-decreasing with minimum increments, each element must be raised to at least the maximum value seen up to that position within the subarray. Thus, the operation cost is the sum of prefix maximums minus the sum of actual array values in that window.
By traversing the left boundary from right to left in reverse, prepending each element allows it to dominate smaller elements as the new running maximum. We maintain an optimal monotonic double-ended queue storing indices where running maximums change, updating total cost dynamically. When the operation cost exceeds k, we contract the right boundary of our sliding window. This reverse two-pointer strategy achieves an optimal O(N) time and O(N) auxiliary space complexity.
π₯ Problem Highlights
β Minimal transformation cost formulated as sum of prefix maximums minus window sum
β Reverse sliding window from right to left maintains clean running prefix maximums
β Monotonic Deque efficiently tracks step-wise prefix maximum contributions
β Dynamic cost checking and two-pointer right boundary shrinking when cost exceeds k
β Amortized O(1) deque push and pop operations per element
β Optimal O(N) time complexity and O(N) auxiliary space complexity
β±οΈ TIMESTAMPS
00:00 Intro
00:34 Problem Understanding
02:02 Observation
03:47 Approach
05:34 Code Explanation
08:13 Code Run
10:08 Time Complexity
10:56 Space Complexity
11:32 Outro
π Problem Folder & Detailed Documentation:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/tree/main/solutions/November/13-November/3420-Count-Non-Decreasing-Subarrays-After-K-Operations
β Java Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/November/13-November/3420-Count-Non-Decreasing-Subarrays-After-K-Operations/Solution.java
π Python Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/November/13-November/3420-Count-Non-Decreasing-Subarrays-After-K-Operations/solution.py
β‘ C++ Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/November/13-November/3420-Count-Non-Decreasing-Subarrays-After-K-Operations/solution.cpp
π JavaScript Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/November/13-November/3420-Count-Non-Decreasing-Subarrays-After-K-Operations/solution.js
π LeetCode Source Code
π https://codebytushu.com/leetcode/problem/count-non-decreasing-subarrays-after-k-operations
π All LeetCode Solutions
π https://codebytushu.com/Leetcode/
π± Join CodeByTushu on WhatsApp
Get coding updates, LeetCode solutions, daily questions and more.
https://whatsapp.com/channel/0029Vb8k5mCDeON2Xwlkxe40
β€οΈ Donate
π https://codebytushu.com/Leetcode/donate.php
π₯ Perfect For
LeetCode Hard Problems
Java DSA Preparation
Monotonic Deque Pattern
Sliding Window Two Pointers
Prefix Sum Range Cost Optimization
Time Complexity Optimization
Coding Interview Preparation
Problem Solving
π Follow CodeByTushu
βΆοΈ YouTube: https://www.youtube.com/@codebytushu
πΈ Instagram: https://instagram.com/codebytushu/
πΌ LinkedIn: https://www.linkedin.com/company/codebytushu/
π Website: https://codebytushu.com
π GitHub: https://github.com/CodeByTushu
β€οΈ Donβt Forget To
π Like | π¬ Comment | π Subscribe
π¬ Question of the Day
In this monotonic deque sliding window approach, why do we traverse the array backwards from right to left?
1οΈβ£ Because prepending an element allows it to act as the new prefix maximum and dominate smaller elements
2οΈβ£ Because Java ArrayDeque only supports operations at the beginning
3οΈβ£ Because it reduces space complexity from O(N) to O(1)
4οΈβ£ Because prefix sum arrays cannot be queried from left to right
#LeetCode3420 #LeetCode #CountNonDecreasingSubarraysAfterKOperations #Java #JavaDSA #MonotonicDeque #SlidingWindow #DSA #CodingInterview #ProblemSolving #LeetCodeHard #DailyLeetCode #JavaProgramming #CodeByTushu
π Comment the answer below! π₯Β Close description
In todayβs video, we solve LeetCode 3420 β Count Non-Decreasing Subarrays After K Operations using Monotonic Deque and Sliding Window in Java.
We are given an integer array nums and an integer k. For any contiguous subarray, we can increment elements up to k times. We need to determine how many subarrays can be transformed into non-decreasing order without exceeding this operation budget. To make a subarray non-decreasing with minimum increments, each element must be raised to at least the maximum value seen up to that position within the subarray. Thus, the operation cost is the sum of prefix maximums minus the sum of actual array values in that window.
By traversing the left boundary from right to left in reverse, prepending each element allows it to dominate smaller elements as the new running maximum. We maintain an optimal monotonic double-ended queue storing indices where running maximums change, updating total cost dynamically. When the operation cost exceeds k, we contract the right boundary of our sliding window. This reverse two-pointer strategy achieves an optimal O(N) time and O(N) auxiliary space complexity.
π₯ Problem Highlights
β Minimal transformation cost formulated as sum of prefix maximums minus window sum
β Reverse sliding window from right to left maintains clean running prefix maximums
β Monotonic Deque efficiently tracks step-wise prefix maximum contributions
β Dynamic cost checking and two-pointer right boundary shrinking when cost exceeds k
β Amortized O(1) deque push and pop operations per element
β Optimal O(N) time complexity and O(N) auxiliary space complexity
β±οΈ TIMESTAMPS
00:00 Intro
00:34 Problem Understanding
02:02 Observation
03:47 Approach
05:34 Code Explanation
08:13 Code Run
10:08 Time Complexity
10:56 Space Complexity
11:32 Outro
π Problem Folder & Detailed Documentation:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/tree/main/solutions/November/13-November/3420-Count-Non-Decreasing-Subarrays-After-K-Operations
β Java Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/November/13-November/3420-Count-Non-Decreasing-Subarrays-After-K-Operations/Solution.java
π Python Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/November/13-November/3420-Count-Non-Decreasing-Subarrays-After-K-Operations/solution.py
β‘ C++ Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/November/13-November/3420-Count-Non-Decreasing-Subarrays-After-K-Operations/solution.cpp
π JavaScript Solution:
https://github.com/CodeByTushu/CodeByTushu-LeetCode-Solutions/blob/main/solutions/November/13-November/3420-Count-Non-Decreasing-Subarrays-After-K-Operations/solution.js
π LeetCode Source Code
π https://codebytushu.com/leetcode/problem/count-non-decreasing-subarrays-after-k-operations
π All LeetCode Solutions
π https://codebytushu.com/Leetcode/
π± Join CodeByTushu on WhatsApp
Get coding updates, LeetCode solutions, daily questions and more.
https://whatsapp.com/channel/0029Vb8k5mCDeON2Xwlkxe40
β€οΈ Donate
π https://codebytushu.com/Leetcode/donate.php
π₯ Perfect For
LeetCode Hard Problems
Java DSA Preparation
Monotonic Deque Pattern
Sliding Window Two Pointers
Prefix Sum Range Cost Optimization
Time Complexity Optimization
Coding Interview Preparation
Problem Solving
π Follow CodeByTushu
βΆοΈ YouTube: https://www.youtube.com/@codebytushu
πΈ Instagram: https://instagram.com/codebytushu/
πΌ LinkedIn: https://www.linkedin.com/company/codebytushu/
π Website: https://codebytushu.com
π GitHub: https://github.com/CodeByTushu
β€οΈ Donβt Forget To
π Like | π¬ Comment | π Subscribe
π¬ Question of the Day
In this monotonic deque sliding window approach, why do we traverse the array backwards from right to left?
1οΈβ£ Because prepending an element allows it to act as the new prefix maximum and dominate smaller elements
2οΈβ£ Because Java ArrayDeque only supports operations at the beginning
3οΈβ£ Because it reduces space complexity from O(N) to O(1)
4οΈβ£ Because prefix sum arrays cannot be queried from left to right
#LeetCode3420 #LeetCode #CountNonDecreasingSubarraysAfterKOperations #Java #JavaDSA #MonotonicDeque #SlidingWindow #DSA #CodingInterview #ProblemSolving #LeetCodeHard #DailyLeetCode #JavaProgramming #CodeByTushu
π Comment the answer below! π₯Β Close description




