BinarySearch 0948 Number of Sublists with Max in Interval

Problem statement

https://binarysearch.com/problems/Number-of-Sublists-with-Max-in-Interval/

Solution

Equal to Leetcode 0795. Number of Subarrays with Bounded Maximum.

Complexity

Time complexity is O(n), space is O(1).

Code

class Solution:
    def solve(self, A, L, R):
        L_ind, R_ind, ans = -1, -1, 0
        for i, num in enumerate(A):
            if num >= L: L_ind = i
            if num > R:  R_ind = i
            ans += L_ind - R_ind
        return ans