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[:i] + nums[j+1:]
            if len(temp) == 0:
                count += 1
                continue
            
            increasing = True
            for k in range(len(temp) - 1):
                if temp[k] >= temp[k+1]:
                    increasing = False
                    break
            if 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 with Two Pointers
def incremovableSubarrayCountOptimized(nums):
    n = len(nums)
    count = 0
    
    for i in range(n + 1):
        for j in range(i, n + 1):
            sub_array = nums[:i] + nums[j:]
            if len(sub_array) <= 1:
                count += 1
                continue
            is_incremovable = all(sub_array[k] < sub_array[k+1] for k in range(len(sub_array)-1))
            if is_incremovable:
                count +=1
    return count


print(f"Optimized - Input: {nums1}, Output: {incremovableSubarrayCountOptimized(nums1)}")
print(f"Optimized - Input: {nums2}, Output: {incremovableSubarrayCountOptimized(nums2)}")
print(f"Optimized - Input: {nums3}, Output: {incremovableSubarrayCountOptimized(nums3)}")

Naive Solution

The naive solution involves iterating through all possible subarrays, removing each subarray from the original array, and then checking if the remaining array is strictly increasing. If it is, we increment a counter. The time complexity of this approach is relatively high because, for each subarray, we need to check if the remaining array is strictly increasing.

Optimal Solution

The optimal solution also involves generating all subarrays but uses a more efficient way of checking if the resulting array is strictly increasing. This can be done by directly verifying the order of elements after creating the subarray.

Time Complexity Analysis

• Naive Solution: O(n^3), where n is the length of the input array nums. This is because we iterate through all possible subarrays (O(n^2)) and, for each subarray, we check if the remaining array is strictly increasing (O(n)).
• Optimized Solution: O(n^3) in the worst-case. The two nested loops to select all possible subarrays contribute O(n^2). Then, constructing the remaining array and checking the strictly increasing condition contributes O(n).

Space Complexity Analysis

• Naive Solution: O(n) because, in the worst case, we create a new list temp that stores the remaining elements after removing a subarray. The length of temp can be up to n (the length of the original array).
• Optimized Solution: O(n) for creating the subarrays, since the max size the array gets is of size n in the worst case.

Edge Cases

1. Empty Array: If the input array is empty, the function should return 0 since there are no subarrays to remove.
2. Single Element Array: If the input array contains only one element, the function should return 1 because removing that single element results in an empty array, which is considered strictly increasing.
3. Array Already Strictly Increasing: If the input array is already strictly increasing, any subarray can be removed, and the remaining array will still be strictly increasing. In this case, the function should return the total number of possible subarrays, which is n *(n+1)/2, where n is the length of the array.
4. Array with Duplicate Elements: The function should correctly handle arrays with duplicate elements and ensure that after removing a subarray, the remaining elements are strictly increasing (i.e., no consecutive elements are equal or decreasing).
5. Array with all the same elements: Removing any sub-array will create an invalid solution.