# Count Subarrays With Fixed Bounds ### **Problem Statement:-** 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. **Link:** [**https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/**](https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/) ### **Problem Explanation with examples:-** **Example 1** ```markdown Input: nums = [4,1,3,5,2,7,5], minK = 1, maxK = 5 Output: 3 Explanation: There are 3 subarrays with fixed bounds: [4,1,3,5], [1,3,5,2], [1,3,5]. All the 3 subarrays have min element = 1 and max element = 5 and are contiguous. ``` **Example 2** ```markdown Input: nums = [1,1,1,1], minK = 1, maxK = 1 Output: 10 Explanation: There are 10 subarrays with fixed bounds: [1], [1,1], [1,1,1], [1,1,1,1], [1], [1,1], [1,1,1], [1], [1,1], [1]. All the 10 subarrays have min element = 1 and max element = 1 and are contiguous. ``` ### Intuition:- * We need something to keep track of contiguous elements as we traverse the array. * We need something to keep track of the min and max elements in the current subarray. * We also need to keep check if any element in our subarray is less than `minK` or greater than `maxK`. * If any element is less than `minK` or greater than `maxK`, we need to reset our subarray. * If we have found `minK` and `maxK` in our subarray, we need to add the number of subarrays that can be formed from the current subarray to our answer. Putting all the above points together, a sliding window approach to solving this problem seems quite feasible. ### Solution:- * We will first replace all the elements in the array that are less than `minK` or greater than `maxK` with -1 so that further on in the code we can easily check if any element is out of bounds. * We will then use a sliding window approach to traverse the array. * We will keep track of the `minK_found` and `maxK_found` in our current subarray. * We will also keep track of the `last_minK_idx` i.e. the index of the last `minK` element in our current subarray and `last_maxK_idx` i.e. the index of the last `maxK` element in our current subarray. * Next, we will keep two variables for the start and end of our sliding window. The variables will be `wind_left` and `wind_right`. * We will keep incrementing the end of our sliding window until we find an element that is less than `minK` or greater than `maxK` which we can identify easily by finding any -1. * If we find any -1, we will reset our subarray by setting `minK_found` and `maxK_found` to 0 and `last_minK_idx` and `last_maxK_idx` to -1. * If we find an element that is greater than or equal to `minK` and less than or equal to `maxK`, we will check if the element is equal to `minK` or `maxK`. * If the element is equal to `minK`, we will set `minK_found` to 1 and `last_minK_idx` to the current index. * If the element is equal to `maxK`, we will set `maxK_found` to 1 and `last_maxK_idx` to the current index. * Parallely, we will also check if `minK_found` and `maxK_found` are both 1 which means we have found `minK` and `maxK` in our current subarray so we will add the number of subarrays that can be formed from the current subarray to our answer by adding `(min(last_minK_idx,last_maxK_idx) - wind_left + 1)` to our answer. * Then just keep repeating the above steps until we reach the end of the array. ### Code:- JAVA Solution ```java class Solution { public int countSubarrays(int[] nums, int minK, int maxK) { int n = nums.length; int[] x = nums.clone(); for (int i = 0; i < n; i++) { if (maxK < x[i] || x[i] < minK) { x[i] = -1; } } int minK_found = 0; int maxK_found = 0; int wind_left = 0; int wind_right = 0; int last_minK_idx = -1; int last_maxK_idx = -1; int ans = 0; while (wind_right < n) { if (x[wind_right] == -1) { minK_found = 0; maxK_found = 0; last_minK_idx = -1; last_maxK_idx = -1; wind_left = wind_right + 1; } if (minK <= x[wind_right] && x[wind_right] <= maxK) { if (x[wind_right] == minK) { minK_found = 1; last_minK_idx = wind_right; } if (x[wind_right] == maxK) { maxK_found = 1; last_maxK_idx = wind_right; } } if (minK_found == 1 && maxK_found == 1) { ans += Math.min(last_minK_idx, last_maxK_idx) - wind_left + 1; } wind_right++; } return ans; } } ``` Python Solution ```python class Solution: def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int: x = nums n = len(nums) for i in range(n): if maxK < x[i] or x[i] < minK: x[i] = -1 minK_found = 0 maxK_found = 0 wind_left = 0 wind_right = 0 last_minK_idx = -1 last_maxK_idx = -1 ans = 0 while wind_right < n: if x[wind_right] == -1: minK_found = 0 maxK_found = 0 last_minK_idx = -1 last_maxK_idx = -1 wind_left = wind_right + 1 if minK <= x[wind_right] <= maxK: if x[wind_right] == minK: minK_found = 1 last_minK_idx = wind_right if x[wind_right] == maxK: maxK_found = 1 last_maxK_idx = wind_right if minK_found == 1 and maxK_found == 1: ans += (min(last_minK_idx,last_maxK_idx) - wind_left + 1) wind_right += 1 return ans ``` ### Complexity Analysis:- **TIME**:- Time complexity is **O(n)** where n is the length of the array nums as we are traversing the array only once. **SPACE**:- Space complexity is **O(1)** as we are not using any extra space. ### References:- * [**Sliding Window**](https://www.geeksforgeeks.org/window-sliding-technique/) * [**Subarray Count**](https://www.geeksforgeeks.org/number-subarrays-maximum-value-given-range/) ### Connect with me:- * [**Twitter**](https://twitter.com/lakshit_cs) * [**Github**](https://github.com/Lakshit-Chiranjiv) * [**LinkedIn**](https://www.linkedin.com/in/lakshit-chiranjiv-sagar-4b0b15198/)