English
2444. 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.
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
Click to open Hints
- Can you solve the problem if all the numbers in the array were between minK and maxK inclusive?
- Think of the inclusion-exclusion principle.
- Divide the array into multiple subarrays such that each number in each subarray is between minK and maxK inclusive, solve the previous problem for each subarray, and sum all the answers.
Solution: #
rs
impl Solution {
pub fn count_subarrays(nums: Vec<i32>, min_k: i32, max_k: i32) -> i64 {
let (mut bad, mut min, mut max) = (-1, -1, -1);
// bad is the index of the first number that is not in the range [min_k, max_k]
let mut res = 0;
for (i, &num) in nums.iter().enumerate() {
let i = i as i64;
// set i to bad index if it is not in the range [min_k, max_k]
if !(min_k <= num && num <= max_k) {
bad = i;
}
// set i to min index if num is equal to min_k
if min_k == num {
min = i;
}
// set i to max index if num is equal to max_k
if max_k == num {
max = i;
}
// it is the last starting point for the subarray
let start = min.min(max);
if start > bad {
res += start - bad; // add the number of subarrays b/w [bad + 1, start]
}
}
res
}
}
... #