Leetcode 0795. Number of Subarrays with Bounded Maximum

Problem statement

https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/

Solution

Let us iterate through numbers and keep index of last number which is >= L and index of last number, which is > R. Then, we can quickly calculate number of subarrays with bounded maximum which ends on symbol with index i: in our window at least one number >= L, no numbers > R, so we calculateL_ind - R_ind. Note, that this number can never be negative, because if num > R then num >= L since L <= R.

Complexity

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

Code

class Solution:
    def numSubarrayBoundedMax(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