Count Subarrays With Fixed Bounds

hard array queue sliding window monotonic queue

Problem

Given nums, minK and maxK, count subarrays whose minimum is minK and maximum is maxK.

Inputnums = [1,3,5,2,7,5], minK = 1, maxK = 5

Output2

Subarrays [1,3,5] and [1,3,5,2].

nums (comma-separated)

minK

maxK

def count_subarrays(nums, min_k, max_k):
    ans = 0
    min_pos = max_pos = bad = -1
    for i, x in enumerate(nums):
        if x < min_k or x > max_k:
            bad = i
        if x == min_k:
            min_pos = i
        if x == max_k:
            max_pos = i
        ans += max(0, min(min_pos, max_pos) - bad)
    return ans

function countSubarrays(nums, minK, maxK) {
  let ans = 0, minPos = -1, maxPos = -1, bad = -1;
  for (let i = 0; i < nums.length; i++) {
    const x = nums[i];
    if (x < minK || x > maxK) bad = i;
    if (x === minK) minPos = i;
    if (x === maxK) maxPos = i;
    ans += Math.max(0, Math.min(minPos, maxPos) - bad);
  }
  return ans;
}

class Solution {
    public long countSubarrays(int[] nums, int minK, int maxK) {
        long ans = 0;
        int minPos = -1, maxPos = -1, bad = -1;
        for (int i = 0; i < nums.length; i++) {
            int x = nums[i];
            if (x < minK || x > maxK) bad = i;
            if (x == minK) minPos = i;
            if (x == maxK) maxPos = i;
            ans += Math.max(0, Math.min(minPos, maxPos) - bad);
        }
        return ans;
    }
}

long long countSubarrays(vector<int>& nums, int minK, int maxK) {
    long long ans = 0;
    int minPos = -1, maxPos = -1, bad = -1;
    for (int i = 0; i < (int)nums.size(); i++) {
        int x = nums[i];
        if (x < minK || x > maxK) bad = i;
        if (x == minK) minPos = i;
        if (x == maxK) maxPos = i;
        ans += max(0, min(minPos, maxPos) - bad);
    }
    return ans;
}

Explanation

A subarray is valid when its minimum is exactly minK and its maximum is exactly maxK. That means it must contain at least one minK, at least one maxK, and no value outside the range [minK, maxK]. We track three positions as we scan to count these in one pass.

For each index i we remember: bad = the last index that was out of range, min_pos = the last index equal to minK, and max_pos = the last index equal to maxK.

A subarray ending at i is valid only if its start is after bad (no out-of-range element) and at or before both min_pos and max_pos (so both endpoints are included). The number of valid starts is min(min_pos, max_pos) - bad, clamped to 0 with max(0, ...).

Example: nums = [1,3,5,2,7,5], minK=1, maxK=5. The 7 at index 4 is out of range and sets bad, cutting off later starts. The valid subarrays counted are [1,3,5] and [1,3,5,2], giving 2.

Since we only update a few variables per element, the whole count is done in a single linear pass.

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