Number of Subarrays with Bounded Maximum — LeetCode 795 Python Solution

The problem

Given an integer array nums and two integers left and right, return the number of contiguous non-empty subarrays such that the value of the maximum array element in that subarray is in the range [left, right]. The test cases are generated so that the answer will fit in a 32-bit integer.

Example

Input

nums = [2,1,4,3], left = 2, right = 3

Output

3

Explanation

There are three subarrays that meet the requirements: [2], [2, 1], [3].

Python solution

class Solution:
    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:
        def f(x):
            cnt = t = 0
            for v in nums:
                t = 0 if v > x else t + 1
                cnt += t
            return cnt

        return f(right) - f(left - 1)

Complexity

Pattern: Two Pointers

Use the order already in the input to discard half the search space at every step. LeetCode 795. Number of Subarrays with Bounded Maximum is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Two Pointers.

The two pointers guide has the Python template for the pattern and the 201 LeetCode problems that use it.

Related problems