Scale Engineer

Count the Number of Incremovable Subarrays I

Easy
#2650Time: O(n³) There are O(n²) possible subarrays. For each subarray, we construct a new list of up to `n` elements, which takes O(n) time. Checking if this list is sorted also takes O(n) time. Therefore, the total time complexity is O(n² * n) = O(n³).Space: O(n) The space complexity is O(n) because, in the worst case, we create a temporary list of size `n-1` to check if the remaining elements are sorted.
Patterns
Two PointersEnumeration
Algorithms
Binary Search
Data structures
Array

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 <= 50
  • 1 <= nums[i] <= 50

Approaches

3 approaches with complexity analysis and trade-offs.

The most straightforward approach is to simulate the process described in the problem. We can generate every possible subarray, conceptually remove it, and then check if the remaining elements form a strictly increasing sequence. If they do, we count that subarray as an "incremovable" one.

Algorithm

  1. Initialize a counter count to 0.
  2. Get the length of the array, n.
  3. Use nested loops to iterate through all possible subarrays nums[i..j].
    • The outer loop for the start index i runs from 0 to n-1.
    • The inner loop for the end index j runs from i to n-1.
  4. For each subarray nums[i..j], simulate its removal by creating a temporary array or list.
    • Add elements from the prefix nums[0..i-1] to the temporary list.
    • Add elements from the suffix nums[j+1..n-1] to the temporary list.
  5. Write a helper function to check if the temporary list is strictly increasing.
    • An empty or single-element list is considered strictly increasing.
    • Iterate through the list and check if temp[k] >= temp[k+1] for any k.
  6. If the temporary list is strictly increasing, increment the count.
  7. After checking all subarrays, return the final count.

Walkthrough

This method involves iterating through all possible start and end indices, i and j, to define a subarray nums[i..j]. For each of these subarrays, we construct a new array that contains all elements of nums except for those in the range [i, j]. Then, we check if this newly formed array is strictly increasing. A helper function can be used for this check. If the check passes, we increment a counter. The total count after checking all subarrays is the answer.

class Solution {    public int incremovableSubarrayCount(int[] nums) {        int n = nums.length;        int count = 0;        for (int i = 0; i < n; i++) {            for (int j = i; j < n; j++) {                if (isIncremovable(nums, i, j)) {                    count++;                }            }        }        return count;    }     private boolean isIncremovable(int[] nums, int start, int end) {        java.util.List<Integer> remaining = new java.util.ArrayList<>();        for (int i = 0; i < start; i++) {            remaining.add(nums[i]);        }        for (int i = end + 1; i < nums.length; i++) {            remaining.add(nums[i]);        }         if (remaining.size() <= 1) {            return true;        }         for (int i = 0; i < remaining.size() - 1; i++) {            if (remaining.get(i) >= remaining.get(i + 1)) {                return false;            }        }        return true;    }}

Complexity

Time

O(n³) There are O(n²) possible subarrays. For each subarray, we construct a new list of up to `n` elements, which takes O(n) time. Checking if this list is sorted also takes O(n) time. Therefore, the total time complexity is O(n² * n) = O(n³).

Space

O(n) The space complexity is O(n) because, in the worst case, we create a temporary list of size `n-1` to check if the remaining elements are sorted.

Trade-offs

Pros

  • Simple to understand and implement.

  • Directly follows the problem statement.

Cons

  • Inefficient due to cubic time complexity.

  • Creates a new list for every subarray check, which consumes extra space and time.

Solutions

class Solution { public int 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 + 1 ) / 2 ; } int 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