# Count Subarrays With Fixed Bounds
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-subarrays-with-fixed-bounds)
Canonical: https://scaleengineer.com/dsa/problems/count-subarrays-with-fixed-bounds
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** Array, Queue, Monotonic Queue
**Companies:** [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley), [Snowflake](https://scaleengineer.com/companies/snowflake), [MathWorks](https://scaleengineer.com/companies/mathworks), [OKX](https://scaleengineer.com/companies/okx)
---
## 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.

**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`

# Approaches
## Brute Force Approach
This approach involves checking every possible subarray of the given array `nums`. For each subarray, we find its minimum and maximum elements and check if they are equal to `minK` and `maxK` respectively. While straightforward, this method is computationally expensive.
**Time:** O(n^2) - Due to the nested loops, where `n` is the number of elements in `nums`. For each starting element, we iterate through the rest of the array. · **Space:** O(1) - We only use a constant amount of extra space for variables.
**Pros:** Simple to understand and implement.; Correct for small input sizes.
**Cons:** Highly inefficient for large arrays.; Will result in a 'Time Limit Exceeded' (TLE) error on competitive programming platforms for the given constraints.
### Explanation
The brute-force method is improved by avoiding redundant calculations. Instead of re-calculating the minimum and maximum for every subarray from scratch, we can maintain the `currentMin` and `currentMax` as we extend the subarray. We use two nested loops. The outer loop sets the start index `i` of a subarray, and the inner loop extends the subarray by moving the end index `j` from `i` to the end of the array. For each subarray `nums[i...j]`, we update the minimum and maximum seen so far and check if they match `minK` and `maxK`. If they do, we increment our counter.

```java
class Solution {
    public long countSubarrays(int[] nums, int minK, int maxK) {
        long count = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int currentMin = nums[i];
            int currentMax = nums[i];
            for (int j = i; j < n; j++) {
                currentMin = Math.min(currentMin, nums[j]);
                currentMax = Math.max(currentMax, nums[j]);
                // If the subarray's bounds are outside [minK, maxK], it can't be a solution,
                // and no extension of it can be a solution either. So we can break.
                if (currentMin < minK || currentMax > maxK) {
                    break;
                }
                if (currentMin == minK && currentMax == maxK) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Loop through the array with an index `i` from 0 to `n-1` to fix the starting point of the subarray.
- Inside this loop, initialize `currentMin` to a very large value and `currentMax` to a very small value.
- Start a nested loop with an index `j` from `i` to `n-1` to fix the ending point of the subarray.
- In the inner loop, update `currentMin` and `currentMax` with the values from the subarray `nums[i...j]`.
- Check if `currentMin` is equal to `minK` and `currentMax` is equal to `maxK`.
- If both conditions are met, increment the `count`.
- After both loops complete, return the total `count`.

## Single Pass Sliding Window
An optimal O(n) solution can be achieved using a single pass and a sliding window concept. The key insight is that any element outside the `[minK, maxK]` range acts as a delimiter, breaking the problem into smaller, independent subproblems. We can iterate through the array, keeping track of the last seen positions of `minK`, `maxK`, and the last out-of-bounds element. For each position, we can calculate how many valid subarrays end at that position.
**Time:** O(n) - We iterate through the array only once, where `n` is the number of elements in `nums`. · **Space:** O(1) - We only use a few variables to store indices, regardless of the input size.
**Pros:** Extremely efficient with linear time complexity.; Uses constant extra space.; Passes all constraints for the problem.
**Cons:** The logic can be slightly more complex to reason about compared to the brute-force approach.
### Explanation
This approach iterates through the array just once. We maintain three crucial indices: `leftBound`, `lastMinK`, and `lastMaxK`. `leftBound` tracks the boundary of the current valid window; any element smaller than `minK` or larger than `maxK` resets this boundary. `lastMinK` and `lastMaxK` store the most recent indices where `minK` and `maxK` were found.

For each element `nums[j]`, we consider it as the end of potential subarrays. A subarray `nums[i...j]` is a fixed-bound subarray if:
1. All its elements are within `[minK, maxK]`. This implies its start index `i` must be greater than `leftBound`.
2. It contains `minK`. This implies `i` must be at or before the last seen `minK`, i.e., `i <= lastMinK`.
3. It contains `maxK`. This implies `i <= lastMaxK`.

Combining these, a valid start index `i` must be in the range `(leftBound, min(lastMinK, lastMaxK)]`. The number of integers in this range is `min(lastMinK, lastMaxK) - leftBound`. We add this number to our total count for each `j`. If `min(lastMinK, lastMaxK)` is not greater than `leftBound`, it means we haven't found both `minK` and `maxK` within the current valid window `(leftBound, j]`, so we add 0.

```java
class Solution {
    public long countSubarrays(int[] nums, int minK, int maxK) {
        long count = 0;
        int leftBound = -1;
        int lastMinK = -1;
        int lastMaxK = -1;

        for (int j = 0; j < nums.length; j++) {
            if (nums[j] < minK || nums[j] > maxK) {
                leftBound = j;
            }
            if (nums[j] == minK) {
                lastMinK = j;
            }
            if (nums[j] == maxK) {
                lastMaxK = j;
            }
            // The number of valid subarrays ending at j is the number of
            // possible start indices i.
            // A valid start index i must be > leftBound and <= min(lastMinK, lastMaxK).
            // The number of such indices is min(lastMinK, lastMaxK) - leftBound.
            // We use Math.max(0, ...) to handle cases where minK or maxK haven't been
            // seen yet in the current window, or they are outside the valid window.
            count += Math.max(0L, (long)Math.min(lastMinK, lastMaxK) - leftBound);
        }
        return count;
    }
}
```
### Algorithm
- Initialize `count = 0L`, and three pointers: `leftBound = -1`, `lastMinK = -1`, `lastMaxK = -1`.
- Iterate through the array `nums` with an index `j` from 0 to `n-1`.
- At each element `nums[j]`, check if it's outside the range `[minK, maxK]`. If it is, update `leftBound = j`, as this element cannot be in any fixed-bound subarray.
- If `nums[j] == minK`, update `lastMinK = j`.
- If `nums[j] == maxK`, update `lastMaxK = j`.
- A subarray ending at `j` is valid if its start index `i` satisfies `leftBound < i <= min(lastMinK, lastMaxK)`.
- The number of such valid start indices is `min(lastMinK, lastMaxK) - leftBound`.
- Add `max(0L, min(lastMinK, lastMaxK) - leftBound)` to the total `count`.
- After the loop finishes, return `count`.

# Solutions
### Java

```java
class Solution {
public
  long countSubarrays(int[] nums, int minK, int maxK) {
    long ans = 0;
    int j1 = -1, j2 = -1, k = -1;
    for (int i = 0; i < nums.length; ++i) {
      if (nums[i] < minK || nums[i] > maxK) {
        k = i;
      }
      if (nums[i] == minK) {
        j1 = i;
      }
      if (nums[i] == maxK) {
        j2 = i;
      }
      ans += Math.max(0, Math.min(j1, j2) - k);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long countSubarrays(vector<int> &nums, int minK, int maxK) {
    long long ans = 0;
    int j1 = -1, j2 = -1, k = -1;
    for (int i = 0; i < nums.size(); ++i) {
      if (nums[i] < minK || nums[i] > maxK)
        k = i;
      if (nums[i] == minK)
        j1 = i;
      if (nums[i] == maxK)
        j2 = i;
      ans += max(0, min(j1, j2) - k);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int: j1 = j2 = k = - 1 ans = 0 for i, v in enumerate(nums): if v < minK or v > maxK: k = i if v == minK: j1 = i if v == maxK: j2 = i ans += max(0, min(j1, j2) - k) return ans

```