LC-2444 Hard LeetCode

2444. Count Subarrays With Fixed Bounds

Array Queue Sliding Window Monotonic Queue

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 69% Topics: Array, Queue, Sliding Window, Monotonic Queue

Reading material

Arrays & Hashing 12 min Stacks & Queues 11 min Sliding Window 11 min

Reference solution (spoiler · python)

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

# two pointers
class Solution(object):
    def countSubarrays(self, nums, minK, maxK):
        """
        :type nums: List[int]
        :type minK: int
        :type maxK: int
        :rtype: int
        """
        result = left = 0
        right = [-1]*2
        for i, x in enumerate(nums):
            if not (minK <= x <= maxK):
                left = i+1
                continue
            if x == minK:
                right[0] = i
            if x == maxK:
                right[1] = i
            result += max(min(right)-left+1, 0)
        return result

Solution from kamyu104/LeetCode-Solutions · MIT