2444. Bounded Subarrays

Count Subarrays With Fixed Bounds

Excellent problem to enhance sliding window technique.

Since We Need Both minK and maxK to Be Bounded

Each time we move window's right end rightIdx, first check whether

$minK \leq nums[rightIdx] \leq maxK$.

If not, $nums[rightIdx]$ falls outside valid range, so no valid subarray with rightIdx as the right end can exist.

Directly reset window's left end leftIdx to rightIdx + 1, and also reset both prevMinIdx and prevMaxIdx to -1,

since we don't yet know whether $nums[leftIdx:]$ contains elements equal to $minK$ or $maxK$.

As Long as $nums[leftIdx: rightIdx + 1]$ Stay Fully In Bounds

We look within window for:

the most recent index $i$ where $nums[i] = minK$, and assign it to prevMinIdx;

the most recent index $j$ where $nums[j] = maxK$, and assign it to prevMaxIdx.

Once both prevMinIdx and prevMaxIdx are not -1, our window has just satisfied the problem's requirements.

Valid subarrays within this window must satisfy three conditions:

(1). Right end exactly at rightIdx

(2). Left end at least at leftIdx, while not exceeding right end

(3). Left end at most at min(prevMinIdx, prevMaxIdx)

(1) and (2) are intuitive. The key is where (3) comes from.

If some index $k$ in the window satisfies min(prevMinIdx, prevMaxIdx) $< k$,

then $nums[k:rightIdx + 1]$ can't contain both $minK$ and $maxK$.

Each bounded subarray is required to contain both $minK$ and $maxK$.

Therefore, number of valid subarrays in current window is:

$C =$ min(prevMinIdx, prevMaxIdx) + 1 - leftIdx

Add $C$ to boundedSubarraysCount, which will be returned at the end.

C++

#include <vector>
using namespace std;

long long countBoundedSubarrays(vector<int>& nums, int minK, int maxK) { // LeetCode Q.2444.
    long long boundedSubarraysCount = 0;

    int prevMinIdx = -1, prevMaxIdx = -1;

    int leftIdx = 0;
    for (int rightIdx = 0; rightIdx < nums.size(); rightIdx++) {
        int num = nums[rightIdx];

        if (num < minK || num > maxK) { // Reset.
            prevMinIdx = -1, prevMaxIdx = -1;
            leftIdx = rightIdx + 1;
            continue;
        }

        if (num == maxK)
            prevMaxIdx = rightIdx;
        if (num == minK)
            prevMinIdx = rightIdx;

        if (min(prevMinIdx, prevMaxIdx) >= 0)
            boundedSubarraysCount += min(prevMinIdx, prevMaxIdx) + 1 - leftIdx;
    }

    return boundedSubarraysCount;
}

Python

def count_bounded_subarrays(nums: list[int], min_k: int, max_k: int):  # LeetCode Q.2444.
    bounded_subarrays_count = 0

    prev_min_idx, prev_max_idx = -1, -1

    left_idx = 0
    for right_idx, num in enumerate(nums):
        if num < min_k or num > max_k:  # Reset.
            prev_min_idx, prev_max_idx = -1, -1
            left_idx = right_idx + 1
            continue

        if num == max_k: prev_max_idx = right_idx
        if num == min_k: prev_min_idx = right_idx

        if min(prev_min_idx, prev_max_idx) >= 0:
            bounded_subarrays_count += min(prev_min_idx, prev_max_idx) + 1 - left_idx

    return bounded_subarrays_count

Time complexity is $O(n)$ where $n$ is input array length. Space is $O(1)$: just four pointers and boundedSubarraysCount to track total.