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

Count Subarrays With Fixed Bounds

Number: 2527

Difficulty: Hard

Paid? No

Companies: Uber, Morgan Stanley, MathWorks, Oracle, Microsoft, Snowflake, Apple, Adobe, Amazon

Problem Description

Given an integer array and two integers minK and maxK, count the number of contiguous subarrays (fixed-bound subarrays) where the minimum value equals minK and the maximum value equals maxK.

Key Insights

  • Use a sliding window to consider only valid segments where every element is between minK and maxK.
  • Keep track of the most recent indices where minK and maxK appeared.
  • Reset the window when an invalid element (less than minK or greater than maxK) is encountered.
  • The number of valid subarrays ending at a position can be determined by the distance from the most recent invalid index to the minimum of the last occurrences of minK and maxK.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the array since we make a single pass. Space Complexity: O(1), as we use only a constant amount of extra space.

Solution

Use a single traversal of the array while maintaining three pointers:

  • lastInvalid: index of the most recent element that is outside the [minK, maxK] range.
  • lastMin: index of the most recent occurrence of minK.
  • lastMax: index of the most recent occurrence of maxK.

For each element:

  1. If it is invalid (not in [minK, maxK]), update lastInvalid.
  2. Update lastMin or lastMax if the element is equal to minK or maxK.
  3. The number of valid subarrays ending at the current index is max(0, min(lastMin, lastMax) - lastInvalid).

Accumulate this count over the array.

Code Solutions

# Python implementation with line-by-line comments

def countSubarrays(nums, minK, maxK):
    # Initialize pointers for last indices of minK, maxK, and invalid element
    last_invalid = -1
    last_min = -1
    last_max = -1
    count = 0
    
    # Loop through all indices in the nums array
    for index, num in enumerate(nums):
        # Check if current number is out of valid range
        if num < minK or num > maxK:
            last_invalid = index  # Reset the last invalid position to current index
        
        # Update last position where minK is found
        if num == minK:
            last_min = index
        
        # Update last position where maxK is found
        if num == maxK:
            last_max = index
        
        # Calculate valid subarray count ending at the current index
        # Only consider subarray if both minK and maxK have been seen after the last invalid index
        valid_start = min(last_min, last_max)
        if valid_start > last_invalid:
            count += valid_start - last_invalid

    return count

# Example usage:
nums = [1, 3, 5, 2, 7, 5]
minK = 1
maxK = 5
print(countSubarrays(nums, minK, maxK))  # Expected output: 2
← Back to All Questions