Scale Engineer

Count the Number of Incremovable Subarrays II

Hard
#2652Time: O(n^2). The nested loops iterate through all `n * (n + 1) / 2` possible subarrays, and the check inside is O(1).Space: O(1). The implementation shown avoids explicit precomputation arrays by finding the bounds `l` and `r`, thus using constant extra space.2 companies
Patterns
Two Pointers
Algorithms
Binary Search
Data structures
Array
Companies
IBMDE Shaw

Prompt

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.

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109

Approaches

3 approaches with complexity analysis and trade-offs.

This approach iterates through all possible subarrays nums[i..j] and, for each one, checks if removing it results in a strictly increasing array. To avoid re-computing whether the remaining parts are sorted for each subarray, we can precompute which prefixes and suffixes of the original array are strictly increasing. This brings the check for each subarray down to O(1), but the overall complexity remains quadratic due to iterating through all subarrays.

Algorithm

  • Precomputation:
    1. Create a boolean array is_prefix_sorted of size n. is_prefix_sorted[i] will be true if the subarray nums[0...i] is strictly increasing.
    2. Create a boolean array is_suffix_sorted of size n. is_suffix_sorted[j] will be true if the subarray nums[j...n-1] is strictly increasing.
    3. These arrays can be filled in O(n) time.
  • Main Logic:
    1. Initialize a counter count to 0.
    2. Iterate through all possible start indices i from 0 to n.
    3. For each i, iterate through all possible end indices j from i-1 to n-1.
      • The subarray to be removed is nums[i...j]. If i > j, the removed subarray is empty, which is not allowed.
    4. For each non-empty subarray nums[i...j]:
      • Check if the prefix nums[0...i-1] is strictly increasing using the precomputed array.
      • Check if the suffix nums[j+1...n-1] is strictly increasing using the precomputed array.
      • If both prefix and suffix are non-empty (i.e., i > 0 and j < n-1), check if nums[i-1] < nums[j+1].
      • If all conditions are met, increment the count.
  • Return count.

Walkthrough

A subarray nums[i..j] is considered 'incremovable' if the array formed by concatenating the prefix nums[0...i-1] and the suffix nums[j+1...n-1] is strictly increasing. This holds true if three conditions are met:

  1. The prefix nums[0...i-1] is strictly increasing.
  2. The suffix nums[j+1...n-1] is strictly increasing.
  3. If both the prefix and suffix are non-empty, the last element of the prefix must be strictly less than the first element of the suffix (i.e., nums[i-1] < nums[j+1]).

To implement this efficiently, we first precompute boolean arrays that tell us if nums[0...k] and nums[k...n-1] are sorted for all k. Then, we can loop through all O(n^2) subarrays and check these conditions in constant time.

class Solution {    public long incremovableSubarrayCount(int[] nums) {        int n = nums.length;        long count = 0;         // Find the longest strictly increasing prefix        int l = 0;        while (l + 1 < n && nums[l] < nums[l + 1]) {            l++;        }         // Find the longest strictly increasing suffix        int r = n - 1;        while (r > 0 && nums[r - 1] < nums[r]) {            r--;        }         for (int i = 0; i < n; i++) { // start index of subarray to remove            for (int j = i; j < n; j++) { // end index of subarray to remove                // Check if prefix nums[0...i-1] is sorted                boolean prefixOk = (i - 1 <= l);                // Check if suffix nums[j+1...n-1] is sorted                boolean suffixOk = (j + 1 >= r);                 if (prefixOk && suffixOk) {                    boolean connectionOk = true;                    if (i > 0 && j < n - 1) {                        if (nums[i - 1] >= nums[j + 1]) {                            connectionOk = false;                        }                    }                    if (connectionOk) {                        count++;                    }                }            }        }        return count;    }}

Complexity

Time

O(n^2). The nested loops iterate through all `n * (n + 1) / 2` possible subarrays, and the check inside is O(1).

Space

O(1). The implementation shown avoids explicit precomputation arrays by finding the bounds `l` and `r`, thus using constant extra space.

Trade-offs

Pros

  • Conceptually simple and directly follows the problem definition.

  • Easier to implement correctly compared to more optimized solutions.

Cons

  • The time complexity of O(n^2) is too slow for the given constraints (n <= 10^5) and will result in a 'Time Limit Exceeded' error on most platforms.

Solutions

class Solution {public  long incremovableSubarrayCount(int[] nums) {    int i = 0, n = nums.length;    while (i + 1 < n && nums[i] < nums[i + 1]) {      ++i;    }    if (i == n - 1) {      return n * (n + 1L) / 2;    }    long ans = i + 2;    for (int j = n - 1; j > 0; --j) {      while (i >= 0 && nums[i] >= nums[j]) {        --i;      }      ans += i + 2;      if (nums[j - 1] >= nums[j]) {        break;      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem