Count Subarrays With Cost Less Than or Equal to K - Solution & Explanation

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.