LeetCode Problem 3835

Difficulty: 🟡 Medium
Topics: Array, Queue, Monotonic Queue

Solution

LeetCode 3835 - Count Subarrays With Cost Less Than or Equal to K

Problem Understanding

We are given an array nums and an integer k.

For every subarray nums[l..r], its cost is defined as:

$$(\max(nums[l..r]) - \min(nums[l..r])) \times (r-l+1)$$

The first part measures the range of values inside the subarray, while the second part measures the length of the subarray.

A subarray is considered valid if its cost is less than or equal to k. Our task is to count how many valid subarrays exist.

The input size is large:

• 1 <= nums.length <= 100000
• 1 <= nums[i] <= 10^9
• 0 <= k <= 10^15

These constraints immediately rule out any solution that examines every subarray individually. Since an array of length 100000 contains about 5 × 10^9 subarrays, even an O(n²) algorithm is far too slow.

The main challenge is efficiently maintaining the maximum and minimum values of a sliding window while determining whether the cost constraint is satisfied.

Several edge cases are worth noting:

• When k = 0, only subarrays whose maximum equals minimum are valid.
• When all values are identical, every subarray has cost 0.
• Very large values of nums[i] require careful handling of integer overflow in languages with fixed-size integers.
• The valid window size may shrink dramatically when a new element creates a much larger range.

Approaches

Brute Force

A straightforward approach is to enumerate every possible subarray.

For each starting index l, extend the ending index r one step at a time. While extending, maintain the current minimum and maximum values. The cost can then be computed as:

$$(\text{maxVal} - \text{minVal}) \times (r-l+1)$$

If the cost is at most k, increment the answer.

This approach is correct because every subarray is examined exactly once and its cost is computed accurately.

However, there are O(n²) subarrays. Even if we maintain the minimum and maximum incrementally, the total runtime remains O(n²), which is infeasible for n = 100000.

Optimal Approach: Sliding Window + Monotonic Queues

The key observation is that the validity condition is monotonic with respect to the left boundary.

For a fixed right endpoint r, suppose a window [l, r] satisfies:

$$(\max - \min) \times \text{length} \le k$$

If we move l to the right, the window becomes shorter. The maximum and minimum may also move closer together. Therefore the cost cannot become larger than before in a way that breaks monotonicity. Once a window becomes valid, every smaller suffix window ending at r is also valid.

This suggests a sliding window approach.

We maintain:

• A deque storing candidates for the maximum value in decreasing order.
• A deque storing candidates for the minimum value in increasing order.

These structures allow us to obtain the current maximum and minimum in O(1) time.

As we extend the right boundary:

1. Insert the new element into both monotonic queues.
2. Check whether the current window violates the cost constraint.
3. If it does, repeatedly move the left boundary rightward until the window becomes valid again.
4. Once the smallest valid left boundary is found, every subarray ending at r and starting from any position between left and r is valid.

Thus we add:

$$r - left + 1$$

to the answer.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Examines every subarray
Optimal	O(n)	O(n)	Sliding window with monotonic queues

Algorithm Walkthrough

1. Initialize two monotonic deques:

• max_deque keeps values in decreasing order.
• min_deque keeps values in increasing order.

2. Initialize:

• left = 0
• answer = 0

3. Iterate right from 0 to n - 1.
4. Insert nums[right] into the maximum deque.

• Remove elements from the back while they are smaller than the new value.
• Append the new index.

5. Insert nums[right] into the minimum deque.

• Remove elements from the back while they are larger than the new value.
• Append the new index.

6. Compute:

• Current maximum from the front of max_deque.
• Current minimum from the front of min_deque.
• Current window length.

7. While:

$$(\text{max} - \text{min}) \times \text{length} > k$$

move left forward. 8. Whenever left advances:

• Remove expired indices from the front of max_deque.
• Remove expired indices from the front of min_deque.

9. After the shrinking process finishes, [left, right] is the largest valid window ending at right.
10. Every subarray ending at right and starting in [left, right] is valid.
11. Add:

$$right - left + 1$$

to the answer. 12. Continue until all positions have been processed.

Why it works

The sliding window always maintains the smallest left boundary such that the current window is valid. Because removing elements from the left can only reduce the window length and cannot increase the range beyond what already exists, validity is monotonic. Therefore, once [left, right] is valid, every suffix window ending at right is also valid. The count right - left + 1 exactly equals the number of valid subarrays ending at right, and summing these counts over all right endpoints gives the total answer.

Python Solution

from collections import deque
from typing import List

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        max_deque = deque()
        min_deque = deque()

        left = 0
        answer = 0

        for right, value in enumerate(nums):
            while max_deque and nums[max_deque[-1]] < value:
                max_deque.pop()
            max_deque.append(right)

            while min_deque and nums[min_deque[-1]] > value:
                min_deque.pop()
            min_deque.append(right)

            while True:
                max_val = nums[max_deque[0]]
                min_val = nums[min_deque[0]]
                length = right - left + 1

                if (max_val - min_val) * length <= k:
                    break

                if max_deque[0] == left:
                    max_deque.popleft()

                if min_deque[0] == left:
                    min_deque.popleft()

                left += 1

            answer += right - left + 1

        return answer

The implementation follows the sliding window strategy exactly.

The two deques store indices rather than values. Using indices allows us to efficiently determine when an element falls outside the current window.

Whenever a new element is added, the monotonic property is restored by removing weaker candidates from the back. The front of each deque always contains the index of the current maximum or minimum.

The inner shrinking loop maintains the validity condition. As soon as the cost becomes less than or equal to k, the window is valid and contributes right - left + 1 subarrays.

Since every index enters and leaves each deque at most once, the total work remains linear.

Go Solution

func countSubarrays(nums []int, k int64) int64 {
	n := len(nums)

	maxDeque := make([]int, 0)
	minDeque := make([]int, 0)

	left := 0
	var answer int64 = 0

	for right := 0; right < n; right++ {
		for len(maxDeque) > 0 &&
			nums[maxDeque[len(maxDeque)-1]] < nums[right] {
			maxDeque = maxDeque[:len(maxDeque)-1]
		}
		maxDeque = append(maxDeque, right)

		for len(minDeque) > 0 &&
			nums[minDeque[len(minDeque)-1]] > nums[right] {
			minDeque = minDeque[:len(minDeque)-1]
		}
		minDeque = append(minDeque, right)

		for {
			maxVal := nums[maxDeque[0]]
			minVal := nums[minDeque[0]]
			length := int64(right - left + 1)

			cost := int64(maxVal-minVal) * length

			if cost <= k {
				break
			}

			if maxDeque[0] == left {
				maxDeque = maxDeque[1:]
			}

			if minDeque[0] == left {
				minDeque = minDeque[1:]
			}

			left++
		}

		answer += int64(right - left + 1)
	}

	return answer
}

The Go implementation mirrors the Python solution. The most important difference is integer handling. Since nums[i] can be as large as 10^9 and the window length can be 10^5, the cost may reach approximately 10^14. Therefore all cost computations are performed using int64.

The deques are implemented as slices of indices. Elements are removed from the front by slicing away the first element.

Worked Examples

Example 1

Input:

nums = [1, 3, 2]
k = 4

right	window after shrinking	max	min	cost	added	total
0	[1]	1	1	0	1	1
1	[1,3]	3	1	4	2	3
2	[3,2]	3	2	2	2	5

Detailed step for right = 2:

Current window [1,3,2]

max = 3
min = 1
length = 3
cost = 6

Invalid, so move left.

Window becomes:

[3,2]
max = 3
min = 2
length = 2
cost = 2

Valid.

Add:

2 - 1 + 1 = 2

Final answer:

5

Example 2

Input:

nums = [5,5,5,5]
k = 0

right	valid count added	running total
0	1	1
1	2	3
2	3	6
3	4	10

Since max = min for every window, the cost is always 0.

Answer:

10

Example 3

Input:

nums = [1,2,3]
k = 0

right	valid window	added	total
0	[1]	1	1
1	[2]	1	2
2	[3]	1	3

Every multi-element window has positive range, therefore positive cost.

Answer:

3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each index enters and leaves each deque at most once
Space	O(n)	Deques may store up to O(n) indices

The critical observation is that no index can be inserted into or removed from a deque more than once. Although there is a nested shrinking loop, the left pointer only moves forward throughout the entire algorithm. Therefore the total number of deque operations is linear, yielding an overall time complexity of O(n).

Test Cases

sol = Solution()

assert sol.countSubarrays([1, 3, 2], 4) == 5  # example 1
assert sol.countSubarrays([5, 5, 5, 5], 0) == 10  # example 2
assert sol.countSubarrays([1, 2, 3], 0) == 3  # example 3

assert sol.countSubarrays([1], 0) == 1  # single element
assert sol.countSubarrays([7], 100) == 1  # single element large k

assert sol.countSubarrays([5, 5], 0) == 3  # all equal
assert sol.countSubarrays([5, 5, 5], 0) == 6  # all equal longer

assert sol.countSubarrays([1, 2], 1) == 3  # boundary equality
assert sol.countSubarrays([1, 2], 0) == 2  # only singletons

assert sol.countSubarrays([1, 1000000000], 10**15) == 3  # very large k
assert sol.countSubarrays([1, 1000000000], 0) == 2  # huge range

assert sol.countSubarrays([1, 2, 1], 2) == 6  # every subarray valid
assert sol.countSubarrays([1, 4, 7], 3) == 3  # only singletons

assert sol.countSubarrays([2, 1, 2, 1, 2], 4) == 15  # alternating values

Test Summary

Test	Why
[1,3,2], 4	Official example
[5,5,5,5], 0	All values identical
[1,2,3], 0	Only singleton windows valid
[1], 0	Smallest possible input
[7], 100	Single element with large k
[5,5]	Equal values, short array
[5,5,5]	Equal values, larger array
[1,2], 1	Cost exactly equals k
[1,2], 0	Cost just exceeds k
[1,1000000000], 10^15	Large numeric values
[1,1000000000], 0	Extreme range with strict limit
[1,2,1], 2	Every subarray valid
[1,4,7], 3	Continuous shrinking required
[2,1,2,1,2], 4	Alternating pattern stresses deques

Edge Cases

k Equals Zero

When k = 0, a subarray is valid only if its maximum and minimum values are identical. A common bug is assuming that every length-one subarray is automatically handled separately. The sliding window naturally handles this case because any window with nonzero range immediately violates the condition and is shrunk until only equal-valued segments remain.

All Elements Are Equal

Consider nums = [5,5,5,5,5]. Every subarray has cost 0, regardless of length. The algorithm correctly keeps expanding the window without ever shrinking it. At position r, it adds r + 1 new valid subarrays, producing the expected total of n(n+1)/2.

Very Large Values and Large k

The values can reach 10^9, while k can reach 10^15. The expression:

$$(\max - \min) \times \text{length}$$

may exceed 32-bit integer limits. The implementation avoids overflow by using Python's arbitrary precision integers and int64 in Go. This ensures correctness even for the largest valid inputs.

Frequent Window Shrinking

Arrays such as [1, 100, 1, 100, 1] can repeatedly force the window to shrink. A naive implementation might recompute maximum and minimum values after every adjustment, leading to quadratic behavior. The monotonic queues guarantee that maximum and minimum retrieval remains O(1), preserving the overall linear runtime.