2444. Count Subarrays With Fixed Bounds

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

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.

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)\).

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top