[LeetCode] Count the Number of Incremovable Subarrays I

10031. Count the Number of Incremovable Subarrays I

You are given a 0-indexed array of positive integers nums.

A subarray of nums is called incremovable if nums becomes strictly increasing on removing the subarray. For example, the subarray [3, 4] is an incremovable subarray of [5, 3, 4, 6, 7] because removing this subarray changes the array [5, 3, 4, 6, 7] to [5, 6, 7] which is strictly increasing.

Return the total number of incremovable subarrays of nums.

Note that an empty array is considered strictly increasing.

A subarray is a contiguous non-empty sequence of elements within an array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
int incremovableSubarrayCount(vector<int>& A) {
A.insert(begin(A),-1);
A.push_back(1e9 + 10);
long long res = 0, le = 0, ri = A.size() - 1, n = A.size();
for(int i = 0; i < n - 1; i++) {
if(A[i] < A[i+1]) le = i+1;
else break;
if(i == n - 2) return (n - 2) * (n - 1) / 2;
}
while(ri - 1 > le and A[ri-1] > A[le] and (ri < n ? A[ri-1] < A[ri] : true)) ri--;
while(le) {
res += (n - ri);
le -= 1;
if(le >= 0) {
while(ri - 1 > le and A[ri-1] > A[le] and (ri < n ? A[ri-1] < A[ri] : true)) ri--;
}
}
res += (n - ri);
return res;
}
};

Author: Song Hayoung
Link: https://songhayoung.github.io/2023/12/24/PS/LeetCode/count-the-number-of-incremovable-subarrays-i/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.