2970. Count the Number of Incremovable Subarrays I LeetCode Solution
In this guide, you will get 2970. Count the Number of Incremovable Subarrays I LeetCode Solution with the best time and space complexity. The solution to Count the Number of Incremovable Subarrays I 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 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.
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 <= 50
1 <= nums[i] <= 50
Complexity Analysis
Time Complexity: O(n\log n)
Space Complexity: O(1)
2970. Count the Number of Incremovable Subarrays I LeetCode Solution in C++
class Solution {
public:
int 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 n * (n + 1) / 2;
// The valid removals starting from nums[0] include nums[0..startIndex - 1],
// nums[0..startIndex], ..., nums[0..n).
int 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 */
2970. Count the Number of Incremovable Subarrays I LeetCode Solution in Java
class Solution {
public int 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 n * (n + 1) / 2;
// The valid removals starting from nums[0] include nums[0..startIndex - 1],
// nums[0..startIndex], ..., nums[0..n).
int 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
2970. Count the Number of Incremovable Subarrays I LeetCode Solution in Python
class Solution:
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
