Count Subarrays With Fixed Bounds

main.md

Question

Approach

When solving this, I realized I needed to find subarrays where the minimum is exactly minK and the maximum is exactly maxK.
To do this efficiently, I tracked three things while scanning nums:

• The last index where the number was out of range (out_idx), meaning it was less than minK or greater than maxK.
• The last index where I saw minK (min_idx).
• The last index where I saw maxK (max_idx).

At each index, if the current number was in range, I checked the smaller of the last seen min_idx and max_idx.
If that index was after out_idx, then it meant a valid fixed-bound subarray ended at the current index, and I added how many such subarrays exist.

Implementation

class Solution:
    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:
        out_idx = -1
        min_idx = -1
        max_idx = -1
        ans = 0

        for i, num in enumerate(nums):
            if num < minK or num > maxK:
                out_idx = i
            if num == minK:
                min_idx = i
            if num == maxK:
                max_idx = i

            valid_start = min(min_idx, max_idx)
            if valid_start > out_idx:
                ans += valid_start - out_idx

        return ans

Complexities

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