algoadvance

You are given an integer array nums and two integers left and right. Return the number of contiguous subarrays where the value of the maximum array element in that subarray is in the range [left, right].

Example:

Clarifying Questions

  1. What are the conditions for the elements of nums?
    • Elements of nums are integers.
  2. What is the range for the values of nums and the bounds left and right?
    • The values of nums, left, and right are all integers, where:
      • 1 <= nums.length <= 10^5
      • 0 <= nums[i] <= 10^9
      • 0 <= left <= right <= 10^9
  3. Are the subarrays contiguous?
    • Yes, the problem specifically requires contiguous subarrays.

Strategy

We’ll utilize a two-pointer approach to solve this problem efficiently:

  1. We’ll iterate through the array using a single pass.
  2. Use two variables:
    • start: to track the beginning of the current subarray.
    • count: to count valid subarrays ending at the current index.
  3. If the current element is within the bounds [left, right], it extends the number of valid subarrays ending at the current index.
  4. If it exceeds right, reset the count of valid subarrays as it breaks the subarray constraint.
  5. If it’s less than left, continue and add previous valid subarrays to the result.

Time Complexity

The time complexity of this solution is O(n) because we iterate through the array once.

Code Implementation

Here is the Python implementation following the above strategy:

def numSubarrayBoundedMax(nums, left, right):
    start = 0
    count = 0
    result = 0
    prev_count = 0
    
    for i in range(len(nums)):
        if left <= nums[i] <= right:
            count = i - start + 1
            prev_count = count
        elif nums[i] < left:
            # This subarray can be part of a valid subarray if previous elements were valid
            count = prev_count
        else: # nums[i] > right
            start = i + 1
            count = 0
            prev_count = 0
        
        result += count
        
    return result

# Example usage:
nums = [2, 1, 4, 3]
left = 2
right = 3
print(numSubarrayBoundedMax(nums, left, right))  # Output: 3

This solution ensures we efficiently count the valid subarrays by only iterating through the list once and keeping track of the count of valid subarrays incrementally.

Try our interview co-pilot at AlgoAdvance.com