How to Solve Number of Subarrays with Bounded Maximum
Number of Subarrays with Bounded Maximum Introduction
Number of Subarrays with Bounded Maximum Introduction
The Number of Subarrays with Bounded Maximum problem presents us with two values, left and right indicating a range. Our task is to design an algorithm that returns the number of contiguous non-empty subarrays such that the maximum array element of the subarray falls within the range. This problem can be simply solved by traversing the array, updating the counter along the way until we find an element greater than the right value which requires us to update our subarray starting value, update our number of valid subarrays with our current counter and reset the counter. This continues until we traverse the full array.
Number of Subarrays with Bounded Maximum Problem
Number of Subarrays with Bounded Maximum Problem
Given an integer array nums and two integers left and right, return the number of contiguous non-empty subarrays such that the value of the maximum array element in that subarray is in the range [left, right].
Example Inputs and Outputs
Example 1
Input: nums = [2,1,4,3], left = 2, right = 3
Output: 3
Example 2
Input: nums = [2,9,2,5,6], left = 2, right = 8
Output: 7
Example 3
Input: nums = [1,2,3,4,5], left = 2, right = 4
Output: 9
Number of Subarrays with Bounded Maximum Solutions
Number of Subarrays with Bounded Maximum Solutions
To solve this problem, we iterate through the given array and maintain two important variables: count and valid_subarrays. We start by initializing both variables to 0. As we traverse the array, if we encounter an element greater than the right value, we update the starting point (subarray_start) to the current element's index and reset the count of valid subarrays to 0. On the other hand, if the current element falls within the range specified by left and right, we calculate the count of valid subarrays starting from the last starting point up to the current element and update (valid_subarrays) accordingly. We keep accumulating the count of valid subarrays in the count variable throughout the process. Finally, we return the count variable, which represents the total number of contiguous non-empty subarrays that fall within the range specified.
def numSubarrayBoundedMax(nums, left, right):
count = 0
subarray_start = -1
valid_subarrays = 0
for i in range(len(nums)):
if nums[i] > right:
subarray_start = i
valid_subarrays = 0
if left <= nums[i] <= right:
valid_subarrays = i - subarray_start
count += valid_subarrays
return count
# Driver code and test cases
nums1 = [2, 1, 4, 3]
left1 = 2
right1 = 3
# Expected output: 3
print(numSubarrayBoundedMax(nums1, left1, right1))
nums2 = [1, 2, 3, 4, 5]
left2 = 2
right2 = 4
# Expected output: 9
print(numSubarrayBoundedMax(nums2, left2, right2))
nums3 = [2, 9, 2, 5, 6]
left3 = 2
right3 = 8
# Expected output: 7
print(numSubarrayBoundedMax(nums3, left3, right3))1def numSubarrayBoundedMax(nums, left, right):
2 count = 0
3 subarray_start = -1
4 valid_subarrays = 0
5
6 for i in range(len(nums)):
7 if nums[i] > right:
8 subarray_start = i
9 valid_subarrays = 0
10
11 if left <= nums[i] <= right:
12 valid_subarrays = i - subarray_start
13
14 count += valid_subarrays
15
16 return count
17
18
19# Driver code and test cases
20nums1 = [2, 1, 4, 3]
21left1 = 2
22right1 = 3
23# Expected output: 3
24print(numSubarrayBoundedMax(nums1, left1, right1))
25
26nums2 = [1, 2, 3, 4, 5]
27left2 = 2
28right2 = 4
29# Expected output: 9
30print(numSubarrayBoundedMax(nums2, left2, right2))
31
32nums3 = [2, 9, 2, 5, 6]
33left3 = 2
34right3 = 8
35# Expected output: 7
36print(numSubarrayBoundedMax(nums3, left3, right3))Time/Space Complexity Analysis
- Time Complexity: O(N), The time complexity is O(N), where N is the length of the input array 'nums'
- Space Complexity: O(1), as we use a constant amount of extra space.
Watch These Related Mock Interviews
About interviewing.io
interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.
