795. Number of Subarrays with Bounded Maximum: https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/description/

number-of-subarrays-with-bounded-maximum.py

# Time: O(n^2) where n is the length of subarrays 
# Space: O(1)
'''
A = [2, 1, 4, 3]
L = 2
R = 3
-----
the # of subarrays that starts with A[i]
2  
2,1
--
1 ✘
--
4 ✘
--
3
'''

class Solution1(object):
    def numSubarrayBoundedMax(self, A, L, R):
        """
        :type A: List[int]
        :type L: int
        :type R: int
        :rtype: int
        """
        i = j = 0
        count = 0
        
        for i in range(len(A)):
            total = 0 
            if A[i] > R:
                continue 
            flag = True 
            j = i
            largest = A[i]
            while j < len(A) and flag:
                largest = max(largest, A[j])
                if largest > R:
                    flag = False
                elif largest < L:
                    j += 1
                else:
                    count += 1
                    j += 1
                
        return count 
 
#############################
#############################
# Time: O(n) where n is the length of subarrays 
# Space: O(1)
'''
A = [0,0,0,1,2,0,0,1,1,0,1]
L = 1
R = 1

OPT[i] = ( the # of subarrays that ends with A[i] ) 
OPT[i-1] + 0 , cntSmall += 1             if A[i] = 0
OPT[i-1] + 1 + cntSmall, cntSmall = 0    if A[i] = 1
0, cntSmall = 0                          if A[i] = 2 
'''

class Solution2(object):
    def numSubarrayBoundedMax(self, A, L, R):
        """
        :type A: List[int]
        :type L: int
        :type R: int
        :rtype: int
        """
        count = 0
        last = 0
        cntSmall = 0
        for num in A:
            if num < L:
                last += 0
                count += last 
                cntSmall += 1
            elif num > R:
                last = 0
                cntSmall = 0
            else:
                last = last + 1 + cntSmall
                cntSmall = 0
                count += last 
        return count