2444. Count Subarrays With Fixed Bounds

You are given an integer array nums and two integers minK and maxK.

A fixed-bound subarray of nums is a subarray that satisfies the following conditions:

• The minimum value in the subarray is equal to minK.
• The maximum value in the subarray is equal to maxK.

Return the number of fixed-bound subarrays.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [1,3,5,2,7,5], minK = 1, maxK = 5
Output: 2
Explanation: The fixed-bound subarrays are [1,3,5] and [1,3,5,2].

Example 2:

Input: nums = [1,1,1,1], minK = 1, maxK = 1
Output: 10
Explanation: Every subarray of nums is a fixed-bound subarray. There are 10 possible subarrays.

Constraints:

• 2 <= nums.length <= 105
• 1 <= nums[i], minK, maxK <= 106

Approach 01:

class Solution {
public:
    long long countSubarrays(vector<int>& nums, int minK, int maxK) {
        long long totalSubarrays = 0;
        int lastMinIndex = -1;
        int lastMaxIndex = -1;
        int lastInvalidIndex = -1;

        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] < minK || nums[i] > maxK)
                lastInvalidIndex = i;
            if (nums[i] == minK)
                lastMinIndex = i;
            if (nums[i] == maxK)
                lastMaxIndex = i;

            int validSubarrayStart = min(lastMinIndex, lastMaxIndex);
            int subarrayCount = validSubarrayStart - lastInvalidIndex;

            totalSubarrays += (subarrayCount > 0) ? subarrayCount : 0;
        }

        return totalSubarrays;
    }
};

class Solution:
    def countSubarrays(self, nums, minK, maxK):
        totalSubarrays = 0
        lastMinIndex = -1
        lastMaxIndex = -1
        lastInvalidIndex = -1

        for i in range(len(nums)):
            if nums[i] < minK or nums[i] > maxK:
                lastInvalidIndex = i
            if nums[i] == minK:
                lastMinIndex = i
            if nums[i] == maxK:
                lastMaxIndex = i

            validSubarrayStart = min(lastMinIndex, lastMaxIndex)
            subarrayCount = validSubarrayStart - lastInvalidIndex

            totalSubarrays += subarrayCount if subarrayCount > 0 else 0

        return totalSubarrays

Time Complexity:

• Single Pass:

  We iterate through the nums array exactly once → \(O(n)\).

• Total Time Complexity:

  \(O(n)\).

Space Complexity:

• Constant Extra Space:

  We use only a few integer variables → \(O(1)\).

• Total Space Complexity:

  \(O(1)\).