Problem

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.

Examples

Example 1:

1
2
3
4
5

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:

1
2
3
4
5

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.

Solution

Method 1 - Count valid subarrays

This problem involves finding subarrays that meet specific constraints, where the minimum value equals minK and the maximum value equals maxK. The strategy is to efficiently traverse the array to count valid subarrays rather than using brute-force methods.

So, first we track bounds:

  • Maintain lastMinK to track the last occurrence of minK.
  • Maintain lastMaxK to track the last occurrence of maxK.
  • Use a lastInvalid pointer to track the last index that invalidates the condition (like elements outside the range [minK, maxK]).

Count the valid subarrays:

  • As we iterate through the array, calculate how far back we can create valid subarrays based on lastMinK and lastMaxK.

So, instead of checking bounds for every possible subarray, maintain positions of these essential values (minK and maxK) to reduce redundant checks.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {

    public long countSubarrays(int[] nums, int minK, int maxK) {
        long ans = 0; // Use long to handle large results
        int lastMinK = -1, lastMaxK = -1, lastInvalid = -1;

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < minK || nums[i] > maxK) {
                lastInvalid = i;
            }

            if (nums[i] == minK) {
                lastMinK = i;
            }

            if (nums[i] == maxK) {
                lastMaxK = i;
            }

            if (lastMinK != -1 && lastMaxK != -1) {
                ans += Math.max(0, Math.min(lastMinK, lastMaxK) - lastInvalid);
            }
        }

        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:
        ans = 0
        lastMinK = lastMaxK = lastInvalid = -1

        for i, num in enumerate(nums):
            if num < minK or num > maxK:
                lastInvalid = i
            
            if num == minK:
                lastMinK = i
            
            if num == maxK:
                lastMaxK = i
            
            if lastMinK != -1 and lastMaxK != -1:
                ans += max(0, min(lastMinK, lastMaxK) - lastInvalid)
        
        return ans

Complexity

  • ⏰ Time complexity: O(n), since we traverse the list once while maintaining constant-time updates for pointers.
  • 🧺 Space complexity: O(1), as we use only a few integer variables for tracking positions, independent of the input size.