~/leetcode $ 2444. Count-Subarrays-With-Fixed-Bounds

EW not a hard question D:. This one is basically like a sliding window approach where we keep track of the index of the last invalid element (element that falls outside of the range), the last minK element and the last maxK element.

Using these indexes, we can calculate how many valid subarrays there are that contain the current index. Calculating this is pretty simple, we need to include minK or maxK so we take the lower index of the two and we CANNOT include the invalid element. So min(minK, maxK) - invalid is the number of valid subarrays (if this is negative, there are no valid subarrays).

We add the number of valid subarrays and return the result.

class Solution(object):
    def countSubarrays(self, nums, minK, maxK):
        """
        :type nums: List[int]
        :type minK: int
        :type maxK: int
        :rtype: int
        """
        res = 0
        invalid = -1
        maxi = -1
        mini = -1

        for i, val in enumerate(nums):
            if not minK <= val <= maxK:
                invalid = i
            if val == minK:
                mini = i
            if val == maxK:
                maxi = i
            
            valid = min(mini, maxi)
            res += max(0, valid - invalid)

        return res

Time Complexity: O(n)

Space Complexity: O(1)

Time Taken: 17m 30s