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:
-
C++
-
Python
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)\).