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.
Example 2:
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.
def incremovableSubarrayCount(nums):
n = len(nums)
count = 0
for i in range(n):
for j in range(i, n):
temp_nums = nums[:i] + nums[j+1:]
if len(temp_nums) <= 1:
count += 1
else:
is_increasing = True
for k in range(len(temp_nums) - 1):
if temp_nums[k] >= temp_nums[k+1]:
is_increasing = False
break
if is_increasing:
count += 1
return count
# Example 1
nums1 = [1, 2, 3, 4]
print(f"Input: {nums1}, Output: {incremovableSubarrayCount(nums1)}")
# Example 2
nums2 = [6, 5, 7, 8]
print(f"Input: {nums2}, Output: {incremovableSubarrayCount(nums2)}")
# Example 3
nums3 = [8, 7, 6, 6]
print(f"Input: {nums3}, Output: {incremovableSubarrayCount(nums3)}")
# Optimized Solution (Two Pointers)
def incremovableSubarrayCountOptimized(nums):
n = len(nums)
count = 0
for left in range(n):
for right in range(left, n):
sub_array = nums[left:right+1]
remaining_array = []
if left > 0:
remaining_array.extend(nums[:left])
if right < n - 1:
remaining_array.extend(nums[right+1:])
is_incremovable = True
if len(remaining_array) > 1:
for i in range(len(remaining_array) - 1):
if remaining_array[i] >= remaining_array[i+1]:
is_incremovable = False
break
if is_incremovable:
count += 1
return count
print(f"\nOptimized Solution:")
# Example 1
nums1 = [1, 2, 3, 4]
print(f"Input: {nums1}, Output: {incremovableSubarrayCountOptimized(nums1)}")
# Example 2
nums2 = [6, 5, 7, 8]
print(f"Input: {nums2}, Output: {incremovableSubarrayCountOptimized(nums2)}")
# Example 3
nums3 = [8, 7, 6, 6]
print(f"Input: {nums3}, Output: {incremovableSubarrayCountOptimized(nums3)}")
# More Optimized Solution (Two Pointers - prefix and suffix)
def incremovableSubarrayCountPrefixSuffix(nums):
n = len(nums)
count = 0
for i in range(n + 1):
for j in range(i, n + 1):
temp = []
if i > 0:
temp.extend(nums[:i])
if j < n:
temp.extend(nums[j:])
is_incremovable = True
for k in range(len(temp) - 1):
if k >= 0 and k + 1 < len(temp) and temp[k] >= temp[k + 1]:
is_incremovable = False
break
if is_incremovable:
count += 1
return count
print(f"\nEven More Optimized Solution:")
# Example 1
nums1 = [1, 2, 3, 4]
print(f"Input: {nums1}, Output: {incremovableSubarrayCountPrefixSuffix(nums1)}")
# Example 2
nums2 = [6, 5, 7, 8]
print(f"Input: {nums2}, Output: {incremovableSubarrayCountPrefixSuffix(nums2)}")
# Example 3
nums3 = [8, 7, 6, 6]
print(f"Input: {nums3}, Output: {incremovableSubarrayCountPrefixSuffix(nums3)}")
Brute Force Solution
The most straightforward solution is to iterate through all possible subarrays, remove each subarray from the original array, and then check if the remaining array is strictly increasing. If it is, increment the count.
Optimal Solution
An optimized solution involves using a two-pointer approach to identify the longest increasing prefix and suffix of the array. The incremovable subarrays can then be counted by considering all combinations of these prefix and suffix subarrays.
Big O Runtime Analysis
Brute Force Solution
The brute force solution has a time complexity of O(n^3), where n is the length of the input array nums. This is because we have nested loops:
- The outer loops iterate through all possible subarrays, which takes O(n^2) time.
- For each subarray, we create a new array and check if it is strictly increasing, which takes O(n) time in the worst case.
Optimized Solution
The two-pointer solution using prefix and suffix has a time complexity of O(n^2), where n is the length of the input array nums.
- The two outer loops take O(n^2) to find all possible sub-arrays
- The inner check if it is strictly increasing takes O(n) time in the worst case.
Big O Space Usage Analysis
Brute Force Solution
The space complexity of the brute force solution is O(n), where n is the length of the input array nums. This is because, in the worst case, the temp_nums list will be a copy of the input array, resulting in O(n) space.
Optimized Solution
The optimized solution has a space complexity of O(n) in the worst case due to the creation of the remaining_array, which in certain scenarios will be the size of the input array.
Edge Cases
- Empty Array: If the input array is empty, the number of incremovable subarrays is 0.
- Array with One Element: If the input array has only one element, there is one incremovable subarray (the array itself).
- Array Already Strictly Increasing: If the input array is already strictly increasing, all possible subarrays are incremovable. The number of such subarrays is n * (n + 1) / 2, where n is the length of the array.
- Array with Duplicate Elements: The presence of duplicate elements affects which subarrays are incremovable. Subarrays that, when removed, leave a remaining array that is not strictly increasing due to the duplicate elements should not be counted.
