# 31.03.2024 [2444. Count Subarrays With Fixed Bounds]
Count subarrays of range `minK..maxK` #hard
31.03.2024
2444. Count Subarrays With Fixed Bounds hard
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/555
Problem TLDR
Count subarrays of range minK..maxK
#hard
Intuition
“all hope abandon ye who enter here”
I’ve failed this question the second time (first was 1 year ago), and still find it very clever.
Consider the safe
space as min(a, b)..max(a,b)
where a
is the last index of minK
and b
is the last index of maxK
. We will remove suffix of 0..j
where j
is a last out of range minK..maxK
.
Let’s examine the trick:
// 1 3 5 2 7 5 1..5
//j
//a
//b
// i
// a
// i
// i
// b +1 = min(a, b) - j = (0 - (-1))
// i +1 = ...same...
another example:
// 0 1 2 3 4 5 6
// 7 5 2 2 5 5 1
//j .
//i .
//a
//b
// i .
// j .
// i .
// b .
// i .
// a . +1
// i
// a +1
// i
// b +3 = 3 - 0
// i
// b +3
The interesting part happens at the index i = 4
: it will update the min(a, b)
, making it a = 3
.
Basically, every subarray starting between j..(min(a, b))
and ending at i
will have minK and maxK, as min(a,b)..max(a,b)
will have them.
Approach
Try to solve it yourself first.
Complexity
Time complexity:
O(n)Space complexity:
O(1)
Code
fun countSubarrays(nums: IntArray, minK: Int, maxK: Int): Long {
var res = 0L; var a = -1; var j = -1; var b = -1
for ((i, n) in nums.withIndex()) {
if (n == minK) a = i
if (n == maxK) b = i
if (n !in minK..maxK) j = i
res += max(0, min(a, b) - j)
}
return res
}
pub fn count_subarrays(nums: Vec<i32>, min_k: i32, max_k: i32) -> i64 {
let (mut res, mut a, mut b, mut j) = (0, -1, -1, -1);
for (i, &n) in nums.iter().enumerate() {
if n == min_k { a = i as i64 }
if n == max_k { b = i as i64 }
if n < min_k || n > max_k { j = i as i64 }
res += (a.min(b) - j).max(0)
}
res
}