2972. Count the Number of Incremovable Subarrays II LeetCode Solution
In this guide, you will get 2972. Count the Number of Incremovable Subarrays II LeetCode Solution with the best time and space complexity. The solution to Count the Number of Incremovable Subarrays II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Count the Number of Incremovable Subarrays II
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.
Example 1:
Input: nums = [1,2,3,4]
Output: 10
Explanation: The 10 incremovable subarrays are: [1], [2], [3], [4], [1,2], [2,3], [3,4], [1,2,3], [2,3,4], and [1,2,3,4], because on removing any one of these subarrays nums becomes strictly increasing. Note that you cannot select an empty subarray.
Input: nums = [6,5,7,8]
Output: 7
Explanation: The 7 incremovable subarrays are: [5], [6], [5,7], [6,5], [5,7,8], [6,5,7] and [6,5,7,8].
It can be shown that there are only 7 incremovable subarrays in nums.
Example 3:
Input: nums = [8,7,6,6]
Output: 3
Explanation: The 3 incremovable subarrays are: [8,7,6], [7,6,6], and [8,7,6,6]. Note that [8,7] is not an incremovable subarray because after removing [8,7] nums becomes [6,6], which is sorted in ascending order but not strictly increasing.
Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 109
Complexity Analysis
Time Complexity: O(n\log n)
Space Complexity: O(1)
2972. Count the Number of Incremovable Subarrays II LeetCode Solution in C++
class Solution {
public:
// Same as 2970. Count the Number of Incremovable Subarrays I
long long incremovableSubarrayCount(vector<int>& nums) {
const int n = nums.size();
const int startIndex = getStartIndexOfSuffix(nums);
// If the complete array is strictly increasing, the total number of ways we
// can remove elements equals the total number of possible subarrays.
if (startIndex == 0)
return static_cast<long>(n) * (n + 1) / 2;
// The valid removals starting from nums[0] include nums[0..startIndex - 1],
// nums[0..startIndex], ..., nums[0..n).
long ans = n - startIndex + 1;
// Enumerate each prefix subarray that is strictly increasing.
for (int i = 0; i < startIndex; ++i) {
if (i > 0 && nums[i] <= nums[i - 1])
break;
// Since nums[0..i] is strictly increasing, find the first index j in
// nums[startIndex..n) such that nums[j] > nums[i]. The valid removals
// will then be nums[i + 1..j - 1], nums[i + 1..j], ..., nums[i + 1..n).
ans += nums.end() -
upper_bound(nums.begin() + startIndex, nums.end(), nums[i]) + 1;
}
return ans;
}
private:
// Returns the start index i of the suffix subarray such that nums[i..n) is
// strictly increasing.
int getStartIndexOfSuffix(const vector<int>& nums) {
for (int i = nums.size() - 2; i >= 0; --i)
if (nums[i] >= nums[i + 1])
return i + 1;
return 0;
}
}; /* code provided by PROGIEZ */
2972. Count the Number of Incremovable Subarrays II LeetCode Solution in Java
class Solution {
// Same as 2970. Count the Number of Incremovable Subarrays I
public long incremovableSubarrayCount(int[] nums) {
final int n = nums.length;
final int startIndex = getStartIndexOfSuffix(nums);
// If the complete array is strictly increasing, the total number of ways we
// can remove elements equals the total number of possible subarrays.
if (startIndex == 0)
return (long) n * (n + 1) / 2;
// The valid removals starting from nums[0] include nums[0..startIndex - 1],
// nums[0..startIndex], ..., nums[0..n).
long ans = n - startIndex + 1;
// Enumerate each prefix subarray that is strictly increasing.
for (int i = 0; i < startIndex; ++i) {
if (i > 0 && nums[i] <= nums[i - 1])
break;
// Since nums[0..i] is strictly increasing, find the first index j in
// nums[startIndex..n) such that nums[j] > nums[i]. The valid removals
// will then be nums[i + 1..j - 1], nums[i + 1..j], ..., nums[i + 1..n).
ans += n - firstGreater(nums, startIndex, nums[i]) + 1;
}
return ans;
}
// Returns the start index i of the suffix subarray such that nums[i..n) is
// strictly increasing.
private int getStartIndexOfSuffix(int[] nums) {
for (int i = nums.length - 2; i >= 0; --i)
if (nums[i] >= nums[i + 1])
return i + 1;
return 0;
}
private int firstGreater(int[] arr, int startIndex, int target) {
final int i = Arrays.binarySearch(arr, startIndex, arr.length, target + 1);
return i < 0 ? -i - 1 : i;
}
} // code provided by PROGIEZ
2972. Count the Number of Incremovable Subarrays II LeetCode Solution in Python
class Solution:
# Same as 2970. Count the Number of Incremovable Subarrays I
def incremovableSubarrayCount(self, nums: list[int]) -> int:
n = len(nums)
startIndex = self._getStartIndexOfSuffix(nums)
# If the complete array is strictly increasing, the total number of ways we
# can remove elements equals the total number of possible subarrays.
if startIndex == 0:
return n * (n + 1) // 2
# The valid removals starting from nums[0] include nums[0..startIndex - 1],
# nums[0..startIndex], ..., nums[0..n).
ans = n - startIndex + 1
# Enumerate each prefix subarray that is strictly increasing.
for i in range(startIndex):
if i > 0 and nums[i] <= nums[i - 1]:
break
# Since nums[0..i] is strictly increasing, find the first index j in
# nums[startIndex..n) such that nums[j] > nums[i]. The valid removals
# will then be nums[i + 1..j - 1], nums[i + 1..j], ..., nums[i + 1..n).
ans += n - bisect.bisect_right(nums, nums[i], startIndex) + 1
return ans
def _getStartIndexOfSuffix(self, nums: list[int]) -> int:
for i in range(len(nums) - 2, -1, -1):
if nums[i] >= nums[i + 1]:
return i + 1
return 0 # code by PROGIEZ
