Problem Informations

• Problem Index: 2444
• Problem Link: Count Subarrays With Fixed Bounds
• Topics: Array, Queue, Sliding Window, Monotonic Queue

Problem Description

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 \leq \text{nums.length} \leq 10^5$
• $1 \leq \text{nums}[i], \text{minK}, \text{maxK} \leq 10^6$

Intuition

The problem requires counting subarrays within a given array nums such that each subarray has both a minimum and a maximum value equal to specified integers minK and maxK, respectively. A brute force method checking all possible subarrays would be inefficient due to potential large input sizes. Hence, an efficient linear scan approach is necessary, employing indices to track positions of interest as the array is traversed.

Approach

The algorithm uses a single pass through the array nums to efficiently count subarrays that match the fixed-bound criteria. Here are the specific steps involved:

1. Initialization:

   • Initialize result to store the number of valid subarrays.
   • Define lastInvalidIndex to keep track of the most recent index where the element is outside the range [minK, maxK].
   • Set minKIndex and maxKIndex to track the most recent indices of minK and maxK, respectively.

2. Iterate through the array:

   • For each element at index right in nums, perform the following:
     • Out of Range Check: If nums[right] is outside the range [minK, maxK], update lastInvalidIndex to right and reset minKIndex and maxKIndex to -1 since the current element cannot be part of a valid subarray.
     • Update Minimum Index: If nums[right] equals minK, update minKIndex to right.
     • Update Maximum Index: If nums[right] equals maxK, update maxKIndex to right.
     • Calculate Subarray Count: When both minK and maxK are found (minKIndex != -1 && maxKIndex != -1), calculate the number of valid subarrays ending at right. The number of such subarrays is given by the difference min(minKIndex, maxKIndex) - lastInvalidIndex.

3. Counting Subarrays: The variable result accumulates the counts of all valid subarrays encountered during the pass through nums.

4. Return the Result: Finally, return result, which contains the total number of fixed-bound subarrays.

This approach ensures that each element is processed in constant time, resulting in an overall time complexity of $O(n)$, where $n$ is the length of nums. This is efficient given the constraints, allowing the solution to handle large inputs effectively.

Code

C++

class Solution {
public:
    long long countSubarrays(vector<int>& nums, int minK, int maxK) {
        long long result = 0;
        int lastInvalidIndex = -1; // Last index of an element that is not in the range [minK, maxK]
        int minKIndex = -1;        // Most recent index of minK in the array
        int maxKIndex = -1;        // Most recent index of maxK in the array

        for (int right = 0; right < nums.size(); ++right) {
            // If the current element is outside the valid range, reset indices
            if (nums[right] < minK || nums[right] > maxK) {
                lastInvalidIndex = right;
                minKIndex = -1;
                maxKIndex = -1;
                continue;
            }

            // Update minKIndex if current element is minK
            if (nums[right] == minK) {
                minKIndex = right;
            }

            // Update maxKIndex if current element is maxK
            if (nums[right] == maxK) {
                maxKIndex = right;
            }

            // If both minK and maxK are found in the current range
            if (minKIndex != -1 && maxKIndex != -1) {
                // Determine the number of valid subarrays ending at 'right'
                result += max(0, min(minKIndex, maxKIndex) - lastInvalidIndex);
            }
        }

        return result;
    }
};

Python

class Solution:
    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:
        result = 0
        lastInvalidIndex = -1  # Last index of an element that is not in the range [minK, maxK]
        minKIndex = -1         # Most recent index of minK in the array
        maxKIndex = -1         # Most recent index of maxK in the array

        for right in range(len(nums)):
            # If the current element is outside the valid range, reset indices
            if nums[right] < minK or nums[right] > maxK:
                lastInvalidIndex = right
                minKIndex = -1
                maxKIndex = -1
                continue

            # Update minKIndex if current element is minK
            if nums[right] == minK:
                minKIndex = right

            # Update maxKIndex if current element is maxK
            if nums[right] == maxK:
                maxKIndex = right

            # If both minK and maxK are found in the current range
            if minKIndex != -1 and maxKIndex != -1:
                # Determine the number of valid subarrays ending at 'right'
                result += max(0, min(minKIndex, maxKIndex) - lastInvalidIndex)

        return result

Complexity

• Time complexity: $O(n)$

  The algorithm iterates through the entire array nums just once using a single loop, making the time complexity $O(n)$, where $n$ is the length of the array. Each operation within the loop, such as condition checking and index updates, takes constant time $O(1)$. Thus, the overall complexity depends linearly on the size of the input array.

• Space complexity: $O(1)$

  The algorithm uses a constant amount of additional space. The space required does not depend on the size of the input nums; it only involves a few integer variables (result, lastInvalidIndex, minKIndex, and maxKIndex). Therefore, the space complexity is $O(1)$.