Count Subarrays With Cost Less Than or Equal to K solution and explanation
9 more videos on this problem
Count Subarrays With Cost Constraint | LeetCode 3835 | Sliding Window & MultisetSanyam IIT Guwahati · 18:45 · 1K views
Count Subarrays With Cost ≤ K 🔥 LeetCode 3835 | Weekly Contest 488 Q3 | Sliding Window + TreeSet Study Placement · 27:11 · 525 views
Count Subarrays With Cost Less Than or Equal to K | Leetcode 3835 | Weekly Contest 488 | Java CodeDeveloper Coder · 19:55 · 398 views
Count Subarrays With Cost Less Than or Equal to K | leetcode 3835 | leetcode weekly contest 488Code Thoughts · 13:00 · 381 views
Leetcode 3835 | Count Subarrays With Cost Less Than or Equal to K | Beginner FriendlyCodeWithMeGuys · 28:43 · 348 views
3835. Count Subarrays With Cost Less Than or Equal to K (Leetcode Medium)Programming Live with Larry · 11:26 · 312 views
LeetCode Problem 3835 | Count Subarrays With Cost Less Than or Equal to KRepovive TV · 13:30 · 140 views
3835.Count Subarrays With Cost Less Than or Equal to K LeetCode Weekly 488 Easiest Approach Dry runBEASTCODES · 18:50 · 47 views
LeetCode 3835 | Count Subarrays With Cost Less Than or Equal to K | Weekly Contest 488 | Coding HelpCodingHelp · 17:00 · 38 views
LeetCode 3835 – Count Subarrays With Cost Less Than or Equal to K | Sliding WindowMonal Gupta · 19:09 · 17 views
The problem
You are given an integer array nums, and an integer k.
For any subarray nums[l..r], define its cost as:
cost = (max(nums[l..r]) - min(nums[l..r])) * (r - l + 1).
Return an integer denoting the number of subarrays of nums whose cost is less than or equal to k.
Example 1:
Input: nums = [1,3,2], k = 4
Output: 5
Explanation:
We consider all subarrays of nums:
nums[0..0]:cost = (1 - 1) * 1 = 0nums[0..1]:cost = (3 - 1) * 2 = 4nums[0..2]:cost = (3 - 1) * 3 = 6nums[1..1]:cost = (3 - 3) * 1 = 0nums[1..2]:cost = (3 - 2) * 2 = 2nums[2..2]:cost = (2 - 2) * 1 = 0
There are 5 subarrays whose cost is less than or equal to 4.
Example 2:
Input: nums = [5,5,5,5], k = 0
Output: 10
Explanation:
For any subarray of nums, the maximum and minimum values are the same, so the cost is always 0.
As a result, every subarray of nums has cost less than or equal to 0.
For an array of length 4, the total number of subarrays is (4 * 5) / 2 = 10.
Example 3:
Input: nums = [1,2,3], k = 0
Output: 3
Explanation:
The only subarrays of nums with cost 0 are the single-element subarrays, and there are 3 of them.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1090 <= k <= 1015
Approach overview
Problem Overview: Given an integer array, count how many subarrays have a computed cost less than or equal to k. The cost depends on values inside the subarray, so the goal is to efficiently expand and shrink windows while tracking the elements that determine that cost.
Approach 1: Brute Force Enumeration (O(n²) time, O(1) space)
Start every subarray from index i and extend it one element at a time to the right. Recompute the cost for each candidate subarray and check whether it is ≤ k. Every valid window increments the answer. This approach is straightforward and useful for verifying logic on small inputs, but it becomes slow for large arrays because it evaluates roughly n² subarrays. No additional data structures are required beyond a few variables.
Approach 2: Sliding Window with Running Statistics (O(n)–O(n log n) time, O(1) space)
Instead of recomputing everything for each subarray, maintain a sliding window using the two pointers technique. The right pointer expands the window while the left pointer shrinks it when the cost exceeds k. Maintaining values like a running sum reduces repeated computation. However, if the cost depends on the maximum element inside the window, updating that value efficiently becomes difficult without additional structure. In the worst case you may still spend extra time recalculating the max element.
Approach 3: Monotonic Deque + Two Pointers (O(n) time, O(n) space)
The optimal solution combines a sliding window with a monotonic queue. As the right pointer moves, push indices into a deque while maintaining decreasing order of values. The front of the deque always stores the maximum element of the current window. At the same time maintain a running sum of the window elements. Using these values you can compute the subarray cost in constant time. If the cost exceeds k, move the left pointer forward, update the sum, and remove indices that fall out of the window from the deque.
Every time the window becomes valid, all subarrays ending at the current right index are valid. Add right - left + 1 to the result. Each element enters and leaves the deque at most once, so the entire algorithm runs in linear time. This technique relies on efficient max retrieval from a deque and is common in problems involving window extremes on an array.
Recommended for interviews: Interviewers expect the sliding window combined with a monotonic deque. Showing the brute force approach first demonstrates problem understanding, but the deque-based solution proves you know how to maintain window maximums in O(1) amortized time and achieve O(n) complexity.
Solution
We notice that if a subarray nums[l..r] has a cost less than or equal to k, then for any l' geq l and r' leq r, the subarray nums[l'..r'] also has a cost less than or equal to k. Therefore, we can enumerate the right endpoint r, use two pointers to maintain the minimum left endpoint l that satisfies the condition, then the number of subarrays ending at r that satisfy the condition is r - l + 1, which we accumulate to the answer.
We can use two deques to maintain the maximum and minimum values in the current window respectively.
The time complexity is O(n) and the space complexity is O(n), where n is the length of the array nums.
class Solution:
def countSubarrays(self, nums: List[int], k: int) -> int:
ans = 0
q1 = deque()
q2 = deque()
l = 0
for r, x in enumerate(nums):
while q1 and nums[q1[-1]] <= x:
q1.pop()
while q2 and nums[q2[-1]] >= x:
q2.pop()
q1.append(r)
q2.append(r)
while l < r and (nums[q1[0]] - nums[q2[0]]) * (r - l + 1) > k:
l += 1
if q1[0] < l:
q1.popleft()
if q2[0] < l:
q2.popleft()
ans += r - l + 1
return ansclass Solution {
public long countSubarrays(int[] nums, long k) {
long ans = 0;
Deque<Integer> q1 = new ArrayDeque<>();
Deque<Integer> q2 = new ArrayDeque<>();
int l = 0;
for (int r = 0; r < nums.length; r++) {
int x = nums[r];
while (!q1.isEmpty() && nums[q1.peekLast()] <= x) {
q1.pollLast();
}
while (!q2.isEmpty() && nums[q2.peekLast()] >= x) {
q2.pollLast();
}
q1.addLast(r);
q2.addLast(r);
while (
l < r && (long) (nums[q1.peekFirst()] - nums[q2.peekFirst()]) * (r - l + 1) > k) {
l++;
if (q1.peekFirst() < l) {
q1.pollFirst();
}
if (q2.peekFirst() < l) {
q2.pollFirst();
}
}
ans += r - l + 1;
}
return ans;
}
}class Solution {
public:
long long countSubarrays(vector<int>& nums, long long k) {
long long ans = 0;
deque<int> q1, q2;
int l = 0;
for (int r = 0; r < nums.size(); r++) {
int x = nums[r];
while (!q1.empty() && nums[q1.back()] <= x) {
q1.pop_back();
}
while (!q2.empty() && nums[q2.back()] >= x) {
q2.pop_back();
}
q1.push_back(r);
q2.push_back(r);
while (l < r && (long long) (nums[q1.front()] - nums[q2.front()]) * (r - l + 1) > k) {
l++;
if (q1.front() < l) {
q1.pop_front();
}
if (q2.front() < l) {
q2.pop_front();
}
}
ans += r - l + 1;
}
return ans;
}
};function countSubarrays(nums: number[], k: number): number {
let ans = 0;
const q1: number[] = [];
const q2: number[] = [];
let h1 = 0,
t1 = 0;
let h2 = 0,
t2 = 0;
let l = 0;
for (let r = 0; r < nums.length; r++) {
const x = nums[r];
while (h1 < t1 && nums[q1[t1 - 1]] <= x) {
t1--;
}
while (h2 < t2 && nums[q2[t2 - 1]] >= x) {
t2--;
}
q1[t1++] = r;
q2[t2++] = r;
while (l < r && (nums[q1[h1]] - nums[q2[h2]]) * (r - l + 1) > k) {
l++;
if (q1[h1] < l) {
h1++;
}
if (q2[h2] < l) {
h2++;
}
}
ans += r - l + 1;
}
return ans;
}func countSubarrays(nums []int, k int64) int64 {
var ans int64 = 0
q1 := make([]int, 0)
q2 := make([]int, 0)
l := 0
for r, x := range nums {
for len(q1) > 0 && nums[q1[len(q1)-1]] <= x {
q1 = q1[:len(q1)-1]
}
for len(q2) > 0 && nums[q2[len(q2)-1]] >= x {
q2 = q2[:len(q2)-1]
}
q1 = append(q1, r)
q2 = append(q2, r)
for l < r &&
int64(nums[q1[0]]-nums[q2[0]])*int64(r-l+1) > k {
l++
if q1[0] < l {
q1 = q1[1:]
}
if q2[0] < l {
q2 = q2[1:]
}
}
ans += int64(r - l + 1)
}
return ans
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n²) | O(1) | Useful for understanding the problem or validating small test cases |
| Sliding Window with Recalculated Max | O(n²) worst case | O(1) | When constraints are moderate and recomputing the max is acceptable |
| Monotonic Deque + Two Pointers | O(n) | O(n) | Optimal solution for large arrays when the cost depends on the window maximum |
Frequently asked questions
Is Count Subarrays With Cost Less Than or Equal to K easy or hard?
The problem is typically classified as Medium difficulty. The main challenge is recognizing that the cost depends on a window extreme and that a monotonic deque can maintain that value efficiently while using a sliding window.
Count Subarrays With Cost Less Than or Equal to K Python/Java solution
Implement the sliding window and maintain a deque for the window maximum. Track the running sum and adjust the left pointer whenever the computed cost becomes greater than k. The same logic works across Python, Java, C++, Go, and TypeScript with O(n) time complexity.
How to solve Count Subarrays With Cost Less Than or Equal to K in O(n)?
Use a two-pointer sliding window and maintain the maximum element with a monotonic deque. As the right pointer expands the window, update the running sum and deque. If the cost exceeds k, move the left pointer forward until the window becomes valid again. For each right index, add the number of valid subarrays ending at that index.
What is the best approach for Count Subarrays With Cost Less Than or Equal to K?
The most efficient solution uses a sliding window with a monotonic deque. The deque keeps track of the maximum element in the current window while two pointers expand and shrink the window. This allows the cost of each subarray to be computed in constant time, resulting in an overall O(n) time complexity.
Is Count Subarrays With Cost Less Than or Equal to K asked at Google/Amazon/Meta?
Problems involving sliding windows and monotonic queues frequently appear in interviews at companies like Amazon, Google, and Meta. Variations that require maintaining a window maximum while counting valid subarrays are particularly common in medium-level interview rounds.
What data structure is used in Count Subarrays With Cost Less Than or Equal to K?
The key data structure is a monotonic deque (monotonic queue). It stores indices in decreasing order of values so the maximum element of the current window is always at the front. This structure enables constant-time maximum queries during sliding window updates.
What is the time complexity of Count Subarrays With Cost Less Than or Equal to K?
The optimal algorithm runs in O(n) time because each element enters and leaves the sliding window at most once. Maintaining the maximum value with a monotonic deque ensures constant amortized time updates. The space complexity is O(n) for the deque structure.