Count Subarrays With Fixed Bounds

class Solution {
public:
    long long countValidSubarrays(vector<int>& arr, int minVal, int maxVal) {
        long long result = 0;
        int lastMin = -1, lastMax = -1, lastInvalid = -1;
        
        for (int idx = 0; idx < arr.size(); ++idx) {
            if (arr[idx] < minVal || arr[idx] > maxVal)
                lastInvalid = idx;
            
            if (arr[idx] == minVal) 
                lastMin = idx;
            if (arr[idx] == maxVal)
                lastMax = idx;

            result += max(0, min(lastMax, lastMin) - lastInvalid);
        }
        return result;
    }
};

This C++ solution for the problem "Count Subarrays With Fixed Bounds" effectively counts all subarrays within an array that meet particular boundary criteria.

• Step to understand approach:

  1. Initialize counters to track occurrences and positions:
     • lastMin: Tracks the last position where the minimum value (minVal) was found.
     • lastMax: Tracks the last position where the maximum value (maxVal) was found.
     • lastInvalid: Tracks the last position of an element that is outside the bounding values.
  2. Loop through each element of the input vector. For each index:
     • Update lastInvalid if the current element does not lie between minVal and maxVal.
     • Update lastMin if the element is equal to minVal.
     • Update lastMax if the element is equal to maxVal.
  3. Calculate the valid subarrays by comparing the positions of lastMin, lastMax, and lastInvalid. Add to the result the number of new valid subarrays that include the current element, which should be at least zero in cases where lastMin or lastMax occurs after lastInvalid.

• Key components:

  • Using the maximum of zero ensures that only valid positions contribute to the count.
  • max function is used to ensure the result is always non-negative, preventing negative counts in scenarios where lastMin or lastMax have not yet been initialized properly before an invalid value.

With these steps, the code efficiently calculates the number of valid subarrays where the values meet the requirements of containing both a minVal and a maxVal without violations, handling edge cases involving elements outside the specified bounds seamlessly.

class Solution {
    public long calculateValidSubarrays(int[] elements, int lowerBound, int upperBound) {
        long subarrayCount = 0;
        int minPos = -1, maxPos = -1, lastInvalid = -1;

        for (int idx = 0; idx < elements.length; ++idx) {
            if (elements[idx] < lowerBound || elements[idx] > upperBound)
                lastInvalid = idx;

            if (elements[idx] == lowerBound)
                minPos = idx;
            if (elements[idx] == upperBound)
                maxPos = idx;

            subarrayCount += Math.max(0, Math.min(maxPos, minPos) - lastInvalid);
        }
        return subarrayCount;
    }
}

The provided Java program defines a method calculateValidSubarrays that counts the number of subarrays in a given array of integers where all elements fit within a specified range, defined by lowerBound and upperBound. Here’s how it works:

• Initialize subarrayCount to count valid subarrays and three pointers minPos, maxPos, and lastInvalid to -1. These pointers track the positions of the minimum value, maximum value, and the most recent element outside the valid range, respectively.
• Iterate over the input array using an index idx.
• If the current element is outside the valid range, update lastInvalid to the current index idx.
• If the current element equals the lowerBound, update minPos to the current index.
• Similarly, if the current element equals the upperBound, update maxPos to the current index.
• Increment the subarrayCount by the difference between the smallest of maxPos or minPos and lastInvalid, making sure this difference is not negative.

The method finally returns the total count of subarrays that satisfy the conditions of having all elements between the lowerBound and upperBound. Ensure to invoke this method by passing a valid array and appropriate bounds to get the count of valid subarrays.

class Solution:
    def validSubarrayCount(self, data: List[int], lower: int, upper: int) -> int:
        res = 0
        low_idx = high_idx = last_invalid = -1
        
        for idx, val in enumerate(data):
            if val < lower or val > upper:
                last_invalid = idx

            if val == lower:
                low_idx = idx
            if val == upper:
                high_idx = idx

            res += max(0, min(low_idx, high_idx) - last_invalid)

        return res

This Python program counts the number of subarrays in a given list data that have all elements within a specified range (lower to upper). It efficiently assesses each element's relation to this range and adjusts indices to tally valid subarrays. Here's how it works:

• Initialize counters and indices: res for the count of valid subarray, low_idx, high_idx for tracking the last occurrences of the lower and upper bounds respectively, and last_invalid for the most recent index of an out-of-bounds element.
• Iterate over the array using a loop. For each element and its index:
  • Check if the element is out of the desired range, updating last_invalid if it is.
  • Update low_idx if the element matches lower.
  • Update high_idx if the element matches upper.
  • Increase res based on the positions of low_idx, high_idx, and last_invalid, calculating possible subarray indices that satisfy the bounds.

Through this method, the code effectively tallies all subarrays where the bounds are respected, ensuring no subarrays include invalid elements outside the specified range. This approach not only keeps track of valid subarray indices but also efficiently excludes invalid sequences without manual checks of subarray contents.