Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

For a subarray ending at the current index, its start must be after the latest out-of-range value and at or before the latest occurrence of each required bound. These three positions determine the full interval of valid starting indices.

Approach

Track the most recent indices of minK, maxK, and any value outside their inclusive range, initializing all to -1. Update them for each new element. Add max(0, min(lastMin, lastMax) - lastOutside) to the answer, counting exactly the allowed starts for that endpoint. Return the accumulated count. When the two bounds are equal, both occurrence indices update together and the same formula correctly counts constant-valued runs.

class Solution:
    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:
        res = 0
        last_out = -1
        mn = -1
        mx = -1

        for i in range(len(nums)):
            # 1. out of baunds
            if nums[i] > maxK or nums[i] < minK:
                last_out = i
            # 2. update mx and mn
            if nums[i] == minK:
                mn = i
            if nums[i] == maxK:
                mx = i
            # 3. add subarrays
            res += max(0, min(mn, mx) - last_out)

        return res

Complexity analysis

Let n = nums.length. Time: O(n) for one last-position scan. Auxiliary space: O(1).