Problem Summary

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

A fixed-bounds subarray is a subarray that satisfies:

1. The minimum value in the subarray is exactly minK
2. The maximum value in the subarray is exactly maxK

Your task is to count how many such subarrays exist.

Example
Input:

nums = [1,3,5,2,7,5], minK = 1, maxK = 5

Valid fixed-bound subarrays:

[1,3,5]
[1,3,5,2]

Output:

2

Constraints

• 1 ≤ nums.length ≤ 10⁵
• All values fit in 32-bit integers
• Must run in O(n)

---

Approach (Simple English)

We must count subarrays where:

• All values lie between minK and maxK
• The subarray contains at least one minK
• The subarray contains at least one maxK

A naive O(n²) approach is too slow.

We need an O(n) sliding-window strategy.

---

Key Insight

For every index i, maintain:

1. lastMin = most recent index where value == minK
2. lastMax = most recent index where value == maxK
3. lastBad = most recent index where value is out of range
   (value < minK or value > maxK)

A valid subarray ending at index i is one whose left boundary is after lastBad
and contains both a minK and a maxK.

The earliest valid start position is:

start = min(lastMin, lastMax)

Thus number of valid subarrays ending at i is:

max(0, start - lastBad)

Why This Works

A subarray that ends at position i is valid if:

• It does not include any bad element → start > lastBad
• The subarray contains both minK and maxK → start <= min(lastMin, lastMax)

We compute this efficiently as we scan once.

---

Java Code (O(n) Sliding Window)

class Solution {
    public long countSubarrays(int[] nums, int minK, int maxK) {

        long count = 0;

        int lastMin = -1; 
        int lastMax = -1;
        int lastBad = -1;

        for (int i = 0; i < nums.length; i++) {

            int x = nums[i];

            if (x < minK || x > maxK) {
                lastBad = i;
            }
            if (x == minK) {
                lastMin = i;
            }
            if (x == maxK) {
                lastMax = i;
            }

            int start = Math.min(lastMin, lastMax);

            if (start > lastBad) {
                count += (start - lastBad);
            }
        }

        return count;
    }
}

---

Dry Run Example

Input:

nums = [1,3,5,2,7,5]
minK = 1, maxK = 5

Variables initially:
lastMin = -1, lastMax = -1, lastBad = -1, count = 0

i = 0 → x = 1

lastMin = 0
start = min(0, -1) → -1
start > lastBad? -1 > -1 → false
count = 0

i = 1 → x = 3

within range
no min or max
start = min(0, -1) → -1
count stays 0

i = 2 → x = 5

lastMax = 2
start = min(0, 2) → 0
0 > -1 → true
count += 0 – (-1) = 1
count = 1
This counts subarray [1,3,5]

i = 3 → x = 2

within range
start still = 0
0 > -1
count += 1
count = 2
This counts [1,3,5,2]

i = 4 → x = 7 (BAD)

lastBad = 4
start = min(0,2) = 0
0 > 4? false
count stays 2

i = 5 → x = 5

lastMax = 5
start = min(0,5) = 0
0 > 4? false
count stays 2

Final Answer = 2

---

Complexity Analysis

Time Complexity:
O(n) — single scan

Space Complexity:
O(1) — constant memory

---

Edge Cases

• If nums never contains minK or maxK → answer is zero
• If all elements are in range and array contains at least one minK and maxK → many valid subarrays
• If many bad values appear, windows are frequently reset
• Works for large arrays up to 10⁵