Count Subarrays With Fixed Bounds — LeetCode 2444 Python Solution

The problem

You are given an integer array nums and two integers minK and maxK. A fixed-bound subarray of nums is a subarray that satisfies the following conditions: The minimum value in the subarray is equal to minK.

Example

Input

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

Output

2

Explanation

The fixed-bound subarrays are [1,3,5] and [1,3,5,2].

Python solution

class Solution:
    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:
        j1 = j2 = k = -1
        ans = 0
        for i, v in enumerate(nums):
            if v < minK or v > maxK:
                k = i
            if v == minK:
                j1 = i
            if v == maxK:
                j2 = i
            ans += max(0, min(j1, j2) - k)
        return ans

Complexity

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 2444. Count Subarrays With Fixed Bounds is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Sliding Window.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Related problems