We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Subarrays with Bounded Maximum

Number: 811

Difficulty: Medium

Paid? No

Companies: Quora, Adobe

Problem Description

Given an integer array nums and two integers left and right, return the number of contiguous non-empty subarrays such that the maximum element in each subarray is between left and right (inclusive).

Key Insights

  • The problem asks for subarrays where the maximum element is within [left, right].
  • Instead of directly counting valid subarrays, we can count subarrays with maximum ≤ right and subtract those with maximum < left.
  • Use a sliding window (or two pointers) approach to efficiently count subarrays in a single pass over the array.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the array, because we iterate over the array a constant number of times. Space Complexity: O(1), as we use a fixed number of extra variables.

Solution

We solve the problem by defining a helper function that counts the number of contiguous subarrays where all elements are less than or equal to a given bound. The number of valid subarrays is equal to:

count_subarrays(right) - count_subarrays(left - 1)

The helper function iterates through the array, and for each element that is less than or equal to the bound, it increments a running count (currentCount). If an element exceeds the bound, the running count resets to zero since it cannot be part of a valid subarray for this count. Adding the currentCount to a global counter gives the total valid subarrays under the current bound.

This approach efficiently manages segments of valid numbers and computes the difference to result in the answer.

Code Solutions

# Python solution for Number of Subarrays with Bounded Maximum

def numSubarrayBoundedMax(nums, left, right):
    # Helper function to count subarrays with max element <= bound
    def count_subarrays(bound):
        count = 0  # Total count of subarrays that satisfy condition
        current_count = 0  # Count for the current valid segment
        for num in nums:
            # If current num is <= bound, it can extend the current valid subarray.
            if num <= bound:
                current_count += 1
            else:
                # If the element is greater than bound, reset count.
                current_count = 0
            count += current_count
        return count

    # Calculate valid subarrays by subtracting subarrays with max < left
    return count_subarrays(right) - count_subarrays(left - 1)

# Example usage:
print(numSubarrayBoundedMax([2,1,4,3], 2, 3))  # Expected output: 3
← Back to All Questions