2972. Count the Number of Incremovable Subarrays II

HardArrayTwo PointersBinary Search
Leetcode Link

Problem Description

You are given an array of positive integers called nums, where the array is indexed starting with 0. The challenge is to find the number of subarrays that can be removed such that the remaining elements of nums form a strictly increasing sequence. A subarray is a contiguous non-empty sequence of elements within an array, and you are tasked with determining all such "incremovable" subarrays. An "incremovable" subarray is one whose removal makes the sequence strictly increasing. An important point to note is that an empty array is always considered strictly increasing.

Here is a quick example to illustrate this: If the array is [5, 3, 4, 6, 7], then the subarray [3, 4] is "incremovable" because upon its removal, we are left with [5, 6, 7], which is strictly increasing.

Intuition

To solve this problem, we approach it by considering different segments of the array that can independently be strictly increasing — the prefix (beginning part) and the suffix (ending part) of the array.

Initially, we find the longest strictly increasing prefix of the nums array. This prefix itself cannot be part of an "incremovable" subarray because its removal would not contribute to making the entire array strictly increasing. However, any subarray that starts immediately after this prefix and extends to the end of the array can be removed to leave a strictly increasing sequence. Thus, we count all subarrays that start at an index greater than the last index of this prefix.

In the next step, we focus on the suffix. We look at each subarray that ends just before a strictly increasing suffix. Here, we must ensure that for any given end index of a subarray, the element just before the subarray must be less than the start of the suffix to keep the entire sequence strictly increasing. We count such arrangements as we identify them.

By carefully examining these two scenarios — looking at the suffixes and prefixes that can remain after removing a subarray — we ensure that all possible "incremovable" subarrays are counted. The final count comprises all valid subarray removals that leave us with a strictly increasing sequence.

Learn more about Two Pointers and Binary Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Solution Approach

The solution uses a two-pointer technique to efficiently find all "incremovable" subarrays. Here's a step-by-step break down of the algorithm, using the Python code provided as a reference:

  1. Initialize a pointer i to start from the beginning of the array. The first step is to increment i until it reaches the end of the longest strictly increasing prefix of nums. This is achieved by a while loop that continues as long as nums[i] is less than nums[i + 1].

  2. If the entire array is strictly increasing (which means i is at the last index after the loop), then every subarray can be considered "incremovable". The total number is calculated using the formula n * (n + 1) // 2 where n is the length of the array nums. This follows from the property that there are n choose 2 plus n subarrays (including the empty subarrays at each position).

  3. If the array is not entirely strictly increasing, the count starts with i + 2, which represents the number of strictly increasing subarrays that include the longest prefix identified in step 1.

  4. A second pointer j is initialized to point to the end of the array. The intention is to decrease j until the strictly increasing suffix is broken (when nums[j - 1] is no longer less than nums[j]).

  5. For each valid position of j, move the pointer i as far back as necessary so that nums[i] is less than nums[j]. At every such step, it represents a possibility where the subarray starting at i + 1 can be removed, and what remains (the prefix up to i and the suffix from j onwards) will be strictly increasing. So, we add i + 2 to our count for each such arrangement.

  6. Continue decrementing j and adjusting i as needed until you've considered all possible endpoints j for the suffix starting from the array's end moving back towards the start (or until the strictly increasing property for the suffix is broken).

This method efficiently finds all the subarrays that can be removed to leave a strictly increasing sequence, as it takes into account all the increasing sequences that can be formed by removing an "incremovable" subarray. It avoids unnecessary repeated work by using two pointers to dynamically adjust the range being considered for possible removal.

This approach is particularly effective because it reduces the problem to a series of decisions about where to start and stop removing elements, which can be determined in O(n) time. The pointer i moves only backward, and the pointer j moves only forward, meaning each element is considered at most twice.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which two pointer technique does Quick Sort use?

Example Walkthrough

Let's take a small example array nums = [2, 1, 3, 5, 4, 6] and walk through the solution approach to find all "incremovable" subarrays that can be removed to leave a strictly increasing sequence.

  1. Identifying the Longest Strictly Increasing Prefix: We set a pointer i at the start of the array and move it forward as long as nums[i] is less than nums[i + 1].

    • Initially, nums[0] = 2 and nums[1] = 1, which is not strictly increasing, so the pointer does not move forward.
    • The longest strictly increasing prefix is of length 0, indicating that there are no strictly increasing elements from the start.

  2. Checking if the Whole Array is Strictly Increasing: Since our pointer i did not reach the last index, the array is not entirely strictly increasing.

    • We don't need to use the formula n * (n + 1) // 2 here, because we found that the first two elements don't form a strictly increasing sequence.
    • The count starts at i + 2, which in this case, is 0 + 2 = 2.

  3. Identifying the Longest Strictly Increasing Suffix: We create a second pointer j at the end of the array and move it backward as long as the strictly increasing suffix is being extended.

    • Starting at j = 5 (last index), since nums[5] = 6 is strictly greater than nums[4] = 4, we decrement j. But we stop at j = 4 because nums[4] = 4 is not strictly greater than nums[3] = 5.

  4. Counting the Possibilities for Removal: For each valid position of j in the strictly increasing suffix, we move i backwards to satisfy nums[i] < nums[j].

    • At j = 4, we find that i = 2, and nums[2] = 3 < nums[4] = 4. So, subarray nums[3:4] (which is [5]) can be removed. Here, i + 2 = 2 + 2 = 4, so we add 4 to our count.

  5. Repeat for Each Valid j Position: We continue to decrement j and adjust i for each potential "incremovable" subarray endpoint.

    • Next, we check j = 3 (since nums[3] = 5 is strictly greater than nums[2] = 3). We cannot move i back any further from i = 2, so we add i + 2 = 4 to our count again.

  6. Aggregate Count and Return: We add up our counts from steps 3 to 5 to get the total number of "incremovable" subarrays that can be removed.

    • Our count is now 2 (base count from step 2) + 4 (from j = 4) + 4 (from j = 3) = 10.

Thus, by using the solution approach, we can efficiently determine that there are 10 "incremovable" subarrays for the array nums = [2, 1, 3, 5, 4, 6]. Each "incremovable" subarray removal would leave a remaining sequence that is strictly increasing.

Solution Implementation

1class Solution:
2    def incremovable_subarray_count(self, nums: List[int]) -> int:
3        # Initialize starting index and get the length of the input list
4        start_index, length = 0, len(nums)
5      
6        # Find the longest increasing prefix of the array
7        while start_index + 1 < length and nums[start_index] < nums[start_index + 1]:
8            start_index += 1
9      
10        # If entire array is increasing, return the sum of length choose 2 plus length
11        if start_index == length - 1:
12            return length * (length + 1) // 2
13      
14        # Count the subarrays including the longest increasing prefix
15        subarray_count = start_index + 2
16      
17        # Start from the end and look for potential non-increasing elements
18        end_index = length - 1
19        while end_index:
20            # Decrease start_index till nums[start_index] is less than nums[end_index]
21            while start_index >= 0 and nums[start_index] >= nums[end_index]:
22                start_index -= 1
23            # Add subarrays count based on the current start_index
24            subarray_count += start_index + 2
25          
26            # If we find a non-increasing pair, break the loop
27            if nums[end_index - 1] >= nums[end_index]:
28                break
29          
30            # Move the end index one step to the left
31            end_index -= 1
32      
33        # Return the total count of incremovable subarrays
34        return subarray_count
35
1class Solution {
2    public long incremovableSubarrayCount(int[] nums) {
3        int increasingSequenceEnd = 0; // Initialize a pointer to track the end of the initial increasing sequence
4        int numsLength = nums.length;  // Assign the length of the array to a variable for easy reference
5
6        // Loop to find the end of the initially increasing sequence
7        while (increasingSequenceEnd + 1 < numsLength && nums[increasingSequenceEnd] < nums[increasingSequenceEnd + 1]) {
8            increasingSequenceEnd++;
9        }
10
11        // If the entire array is an increasing sequence, return the count of all possible subarrays.
12        if (increasingSequenceEnd == numsLength - 1) {
13            return numsLength * (numsLength + 1L) / 2; // n(n+1)/2 is the formula for the sum of all natural numbers up to n.
14        }
15
16        long answer = increasingSequenceEnd + 2; // Initialize the answer and start counting from increasingSequenceEnd + 2
17
18        // Loop from the end of the array to the start
19        for (int j = numsLength - 1; j > 0; --j) {
20
21            // Decrease increasingSequenceEnd pointer until the value at it is less than the value at index 'j'.
22            while (increasingSequenceEnd >= 0 && nums[increasingSequenceEnd] >= nums[j]) {
23                --increasingSequenceEnd;
24            }
25
26            // Update the answer with the possible subarray counts calculated using the current index 'j'.
27            answer += increasingSequenceEnd + 2;
28
29            // If the previous number is not less than the current, there's no point in continuing.
30            if (nums[j - 1] >= nums[j]) {
31                break;
32            }
33        }
34
35        return answer; // Return the total count of incremovable subarrays.
36    }
37}
38
1class Solution {
2public:
3    // Function to count the number of increasing subarrays that can be formed such that 
4    // any subarray can only be removed as a whole if it is strictly increasing.
5    long long incremovableSubarrayCount(vector<int>& nums) {
6        int currentPos = 0;
7        int n = nums.size();
8
9        // Finding the initial strictly increasing sequence
10        while (currentPos + 1 < n && nums[currentPos] < nums[currentPos + 1]) {
11            ++currentPos;
12        }
13
14        // If the entire array is strictly increasing, return the sum of all possible
15        // subarray lengths (which follows the formula n * (n + 1) / 2 for consecutive
16        // integers starting from 1).
17        if (currentPos == n - 1) {
18            return static_cast<long long>(n) * (n + 1) / 2;
19        }
20
21        // Start counting the strictly increasing subarrays
22        long long count = currentPos + 2;
23
24        // Traverse the array from the end, looking for strictly increasing sequences
25        // from the back and count all the possible subarrays.
26        for (int reversePos = n - 1; reversePos > 0; --reversePos) {
27            // Decrement currentPos until a valid subarray (strictly increasing) emerges.
28            while (currentPos >= 0 && nums[currentPos] >= nums[reversePos]) {
29                --currentPos;
30            }
31
32            // Add possible subarrays starting at positions up to currentPos.
33            count += currentPos + 2;
34
35            // Stop if the next sequence is not strictly increasing.
36            if (nums[reversePos - 1] >= nums[reversePos]) {
37                break;
38            }
39        }
40
41        return count;
42    }
43};
44
1// Function to count the number of incrementally removable subarrays in a given array
2function incremovableSubarrayCount(nums: number[]): number {
3    const n = nums.length; // Number of elements in the array
4    let index = 0;
5  
6    // Find the length of the initial increasing subarray
7    while (index + 1 < n && nums[index] < nums[index + 1]) {
8        index++;
9    }
10  
11    // If the whole array is increasing, return the sum of all subarray counts
12    if (index === n - 1) {
13        return (n * (n + 1)) / 2;
14    }
15  
16    // Initial count including subarrays ending at the first non-increasing element
17    let count = index + 2;
18  
19    // Iterate from the end of the array to find all other incremovable subarrays
20    for (let reverseIndex = n - 1; reverseIndex > 0; --reverseIndex) {
21        // Decrease index while the current value is not less 
22        // than the value at reverseIndex to maintain increasing order
23        while (index >= 0 && nums[index] >= nums[reverseIndex]) {
24            --index;
25        }
26      
27        // Increment count by the number of incremovable subarrays
28        // which can be created ending with nums[reverseIndex]
29        count += index + 2;
30
31        // If we find a non-increasing pair from the end, we stop the process
32        if (nums[reverseIndex - 1] >= nums[reverseIndex]) {
33            break;
34        }
35    }
36  
37    // Return the total count of incremovable subarrays
38    return count;
39}
40
Not Sure What to Study? Take the 2-min Quiz：

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(n). Here's why:

  • The first while loop increments i until the sequence is no longer strictly increasing. In the worst case scenario, this will take O(n) time if nums is an increasing array.
  • The if condition checks if the entire array is increasing and, if so, returns a calculation based on the length of nums, which is an O(1) operation.
  • The second while loop (starting with while j:) potentially iterates from the end of the array down to the beginning. Each nested while loop (under while j:) will reduce i until a suitable condition is met. Together, both loops will at most go through the array once in reverse, leading again to O(n) time.

Combining both loops, our time complexity remains O(n) since both loops can't exceed n iterations in total for the length of the array.

Space Complexity

The space complexity of the code is O(1). This is because:

  • The variables i, n, ans, and j use a constant amount of space that does not depend on the size of the input nums.
  • No additional data structures that grow with input size are used.
  • Thus, the space used remains constant irrespective of the length of nums.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Recommended Readings

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe Two pointers is a common interview technique

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫