Count Subarrays With Fixed Bounds

Problem Description

You are given an integer array nums and two integers minK and maxK. A fixed-bound subarray of nums is a subarray that satisfies the following conditions:

• The minimum value in the subarray is equal to minK.
• The maximum value in the subarray is equal to maxK.

Return the number of fixed-bound subarrays.

Key Insights

• A subarray must contain both minK and maxK to be considered a fixed-bound subarray.
• The presence of values outside the range [minK, maxK] will break potential subarrays.
• Efficiently counting valid subarrays can be achieved using a sliding window approach.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we can utilize a sliding window technique:

1. Traverse the array while maintaining two pointers to represent the bounds of the current subarray.
2. Track the last positions of minK and maxK within the current valid window.
3. For each valid subarray ending at the current index, count all subarrays that can be formed starting from valid positions of minK and maxK.
4. Reset the pointers when a value outside the range [minK, maxK] is encountered.

This approach ensures we only pass through the array once, making it efficient.

Code Solutions