Difficulty: Easy | Acceptance: 56.50% | Paid: No Topics: Array, Two Pointers, Binary Search, Enumeration
You are given a 0-indexed array nums of length n.
A subarray is called incremovable if removing it makes the remaining elements strictly increasing.
Return the number of incremovable subarrays of nums.
A subarray is a contiguous non-empty sequence of elements within the array.
Table of Contents
- Examples
- Constraints
- Brute Force
- Prefix-Suffix with Binary Search
- Two Pointers
Examples
Example 1:
Input: nums = [1,2,3,4]
Output: 10
Explanation: All 10 subarrays are incremovable.
Example 2:
Input: nums = [6,5,7,8]
Output: 7
Explanation: The 7 incremovable subarrays are:
- [5,7,8]
- [6,5,7,8]
- [6,5,7]
- [6,5]
- [5]
- [7]
- [8]
Example 3:
Input: nums = [8,7,6,6]
Output: 3
Explanation: The 3 incremovable subarrays are:
- [8,7,6]
- [7]
- [8]
Constraints
1 <= nums.length <= 50
1 <= nums[i] <= 50
Brute Force
Intuition For each possible subarray, remove it and check if the remaining elements form a strictly increasing sequence.
Steps
- Iterate over all possible starting indices l
- For each l, iterate over all possible ending indices r (r >= l)
- For each subarray [l, r], check if the remaining elements are strictly increasing
- Count all valid subarrays
from typing import List
class Solution:
def incremovableSubarrayCount(self, nums: List[int]) -> int:
n = len(nums)
count = 0
for l in range(n):
for r in range(l, n):
valid = True
prev = None
for i in range(n):
if l <= i <= r:
continue
if prev is not None and nums[i] <= prev:
valid = False
break
prev = nums[i]
if valid:
count += 1
return count
Complexity
- Time: O(n³)
- Space: O(1)
- Notes: Simple but inefficient for larger arrays. Works well for the given constraints (n ≤ 50).
Prefix-Suffix with Binary Search
Intuition Precompute the longest strictly increasing prefix and suffix. For each valid prefix ending position, use binary search to find compatible suffix starting positions.
Steps
- Find the longest strictly increasing prefix (index
left) - Find the longest strictly increasing suffix (starting index
right) - Handle special case where entire array is strictly increasing
- Count subarrays starting from index 0
- For each valid prefix ending position, use binary search to count valid suffix combinations
from bisect import bisect_right
from typing import List
class Solution:
def incremovableSubarrayCount(self, nums: List[int]) -> int:
n = len(nums)
left = 0
while left < n - 1 and nums[left] < nums[left + 1]:
left += 1
if left == n - 1:
return n * (n + 1) // 2
right = n - 1
while right > 0 and nums[right - 1] < nums[right]:
right -= 1
count = n - (right - 1)
for l in range(1, left + 2):
count += 1
lo = bisect_right(nums, nums[l - 1], right, n)
count += n - lo
return count
Complexity
- Time: O(n log n)
- Space: O(1)
- Notes: More efficient than brute force. Binary search leverages the sorted nature of the suffix.
Two Pointers
Intuition Since both the prefix and suffix are strictly increasing, we can use two pointers instead of binary search. As we move through the prefix, the suffix pointer only moves forward.
Steps
- Find the longest strictly increasing prefix and suffix
- Handle the special case where the entire array is strictly increasing
- Count subarrays starting from index 0
- Use two pointers: iterate through valid prefix endings while advancing the suffix pointer to find compatible starting positions
from typing import List
class Solution:
def incremovableSubarrayCount(self, nums: List[int]) -> int:
n = len(nums)
left = 0
while left < n - 1 and nums[left] < nums[left + 1]:
left += 1
if left == n - 1:
return n * (n + 1) // 2
right = n - 1
while right > 0 and nums[right - 1] < nums[right]:
right -= 1
count = n - (right - 1)
j = right
for l in range(1, left + 2):
count += 1
while j < n and nums[j] <= nums[l - 1]:
j += 1
count += n - j
return count
Complexity
- Time: O(n)
- Space: O(1)
- Notes: Optimal solution. The two pointers technique eliminates the need for binary search since both sequences are sorted.