LC-0795 Medium LeetCode

795. Number of Subarrays with Bounded Maximum

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 54% Topics: Array, Two Pointers

Reading material

Arrays & Hashing 12 min Two Pointers 9 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(1)

class Solution(object):
    def numSubarrayBoundedMax(self, A, L, R):
        """
        :type A: List[int]
        :type L: int
        :type R: int
        :rtype: int
        """
        def count(A, bound):
            result, curr = 0, 0
            for i in A :
                curr = curr + 1 if i <= bound else 0
                result += curr
            return result

        return count(A, R) - count(A, L-1)

Solution from kamyu104/LeetCode-Solutions · MIT