Count the Number of Incremovable Subarrays I — Solution
Count the Number of Incremovable Subarrays I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Count the Number of Incremovable Subarrays I is an easy coding problem on arrays, two pointers and enumeration, asked in Amazon, Google and Wipro interviews.
- Difficulty: Easy
- Topics: Arrays, Two Pointers, Enumeration
- Asked at: Amazon, Google, Wipro
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A subarray is incremovable if removing it leaves the array strictly increasing. The empty array counts as strictly increasing, and a subarray must be non-empty and contiguous.
Return the number of incremovable subarrays of nums.
Example 1
Input: nums = [1,2,3,4]
Output: 10
Explanation: Already increasing, so every one of the 10 subarrays qualifies.
Example 2
Input: nums = [6,5,7,8]
Output: 7
Explanation: Removing `[7]`, `[7,8]` or `[8]` leaves the `6,5` descent in place.
Example 3
Input: nums = [8,7,6,6]
Output: 3
Explanation: Only `[8,7,6]`, `[8,7,6,6]` and `[7,6,6]` work.
Constraints
1 <= nums.length <= 501 <= nums[i] <= 50
Hints for Count the Number of Incremovable Subarrays I
Hint 1
With
n <= 50there are at most 1275 subarrays — each one can simply be tested.Hint 2
After removing
nums[i..j], the remainder is the prefix beforeifollowed by the suffix afterj.Hint 3
Removing everything leaves the empty array, which counts.
How to solve Count the Number of Incremovable Subarrays I
Enumerate every subarray [i..j] and check whether the concatenation of the untouched prefix and suffix is strictly increasing. At n <= 50 this direct check is fast enough, and it is the version of the problem where clarity beats cleverness.
Approach
- For each pair
i <= j, walk the array skipping indicesithroughj. - Track the previous surviving value and fail as soon as a value is not strictly greater.
- Count the pairs that survive.
Why it works
Walking the array with the removed range skipped avoids building a new array per candidate, so the inner check is a single pass with no allocation. The linear-time solution required by version II instead finds the longest increasing prefix and suffix and pairs them with two pointers — but at this size the cubic enumeration is under 150 000 steps.
Complexity
- Time —
O(n³) - Space —
O(1)
Pitfalls
- The whole array is a valid subarray, and removing it leaves the empty array — which counts.
- "Strictly" increasing: equal adjacent survivors fail.
- The prefix and suffix must also be increasing across the join, not just internally.
Reference solution
Python
from typing import List
def incremovableSubarrayCount(nums: List[int]) -> int:
n = len(nums)
count = 0
for i in range(n):
for j in range(i, n):
ok = True
prev = -1
for t in range(n):
if i <= t <= j:
continue
if prev != -1 and nums[t] <= prev:
ok = False
break
prev = nums[t]
if ok:
count += 1
return countJava
public static int incremovableSubarrayCount(int[] nums) {
int n = nums.length, count = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
boolean ok = true;
int prev = -1;
for (int t = 0; t < n; t++) {
if (t >= i && t <= j) continue;
if (prev != -1 && nums[t] <= prev) { ok = false; break; }
prev = nums[t];
}
if (ok) count++;
}
}
return count;
}C++
int incremovableSubarrayCount(vector<int>& nums) {
int n = (int) nums.size(), count = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
bool ok = true;
int prev = -1;
for (int t = 0; t < n; t++) {
if (t >= i && t <= j) continue;
if (prev != -1 && nums[t] <= prev) { ok = false; break; }
prev = nums[t];
}
if (ok) count++;
}
}
return count;
}JavaScript
var incremovableSubarrayCount = function(nums) {
var n = nums.length, count = 0;
for (var i = 0; i < n; i++) {
for (var j = i; j < n; j++) {
var ok = true, prev = -1;
for (var t = 0; t < n; t++) {
if (t >= i && t <= j) continue;
if (prev !== -1 && nums[t] <= prev) { ok = false; break; }
prev = nums[t];
}
if (ok) count++;
}
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Two Pointers Technique