Number Of Subarrays With Bounded Maximum - Leetcode Solution

Problem:

Given an integer array nums and two integers left and right, return the number of contiguous non-empty subarrays in nums that lie in the range [left, right].

The length of a subarray is the number of elements in that subarray.

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].

Solution:

The brute force approach of this problem is to generate all possible subarrays and count the number of subarrays that satisfy the given condition. However, this approach will have a time complexity of O(n^3), which is not efficient enough.

A better approach is to use a sliding window technique to count the number of subarrays that satisfy the given condition. We will maintain two pointers, i and j, and a count of the number of subarrays that satisfy the given condition.

Initially, we set i and j to zero and count to zero. We iterate through the array and check if the current element is between the left and right bounds. If it is, we expand the window by moving j to the right and add the number of subarrays in the current window to the count.

If the current element is less than the left bound, we reset the window by setting i to j+1 and j to i. If the current element is greater than the right bound, we just move j to the right.

At each iteration, we add the number of subarrays in the current window to the count. The number of subarrays in the current window is simply the difference between j and i + 1, as it includes all subarrays starting from i and ending at j.

Finally, we return the count.

Implementation:

We can implement the above algorithm in Python as follows:

def numSubarrayBoundedMax(nums, left, right): i, j, count = 0, 0, 0 for k in range(len(nums)): if nums[k] >= left and nums[k] <= right: j = k count += j - i + 1 elif nums[k] < left: j = k elif nums[k] > right: i = k + 1 j = i return count

We start by initializing i, j and count to zero. We loop through all the elements of the array and apply the sliding window algorithm described above.

We return the count of subarrays that satisfy the given condition.

Time Complexity: O(n), where n is the length of the input array.

Space Complexity: O(1).

1