Count the Number of Incremovable Subarrays II

Hard

Asked by:

18 views

Topics:

ArraysTwo Pointers

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 <= 10⁵
1 <= nums[i] <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the length and the values within the input array, `nums`? Are there any limitations on the range of integers?
Can the input array `nums` contain duplicate values, and if so, how should those duplicates be handled when determining if a subarray is incremovable?
Is an empty array considered an incremovable subarray, and if so, how should I handle the case where the entire input array is empty?
Could you please clarify what constitutes an 'incremovable' subarray? Specifically, what does it mean for the 'remaining' array to be strictly increasing after removing the subarray? Does 'strictly increasing' imply that `nums[i] < nums[i+1]`?
If there are multiple incremovable subarrays, do I need to return all possible subarrays or just the count of all such subarrays?

Brute Force Solution

Approach

The brute force strategy to count incremovable subarrays involves checking every possible subarray that can be removed from the original sequence. We verify, for each possible removal, if the remaining sequence satisfies the incremovable property, meaning it's strictly increasing.

Here's how the algorithm would work step-by-step:

Consider every possible subarray that could be removed from the original sequence.
For each of these potential removals, create a new sequence by removing the selected subarray from the original sequence.
Check if the remaining sequence is strictly increasing. That is, each number must be greater than the one before it.
If the remaining sequence is strictly increasing, count that removal as a valid incremovable subarray.
Repeat these steps until every possible subarray has been considered and checked.
The final answer will be the total count of the valid incremovable subarrays.

Code Implementation

def count_incremovable_subarrays_brute_force(sequence):
    sequence_length = len(sequence)
    incremovable_subarray_count = 0

    # Iterate through all possible start indices of subarrays to remove
    for start_index_to_remove in range(sequence_length):
        # Iterate through all possible end indices of subarrays to remove
        for end_index_to_remove in range(start_index_to_remove, sequence_length):
            # Create a new sequence by removing the subarray
            remaining_sequence = sequence[:start_index_to_remove] + sequence[end_index_to_remove + 1:]

            # Check if the remaining sequence is strictly increasing
            is_strictly_increasing = True
            for index in range(1, len(remaining_sequence)):
                if remaining_sequence[index] <= remaining_sequence[index - 1]:
                    is_strictly_increasing = False
                    break

            # Increment the counter if the remaining sequence is incremovable
            if is_strictly_increasing:
                incremovable_subarray_count += 1

    return incremovable_subarray_count

def count_incremovable_subarrays_ii(sequence):
    sequence_length = len(sequence)
    incremovable_subarrays_count = 0

    for start_index in range(sequence_length):
        for end_index in range(start_index, sequence_length):
            # Create the remaining sequence after removing the subarray.
            removed_sequence = sequence[:start_index] + sequence[end_index+1:]

            if len(removed_sequence) <= 1:
                incremovable_subarrays_count += 1
                continue

            # Check if the remaining array is strictly increasing.
            is_incremovable = True
            for index in range(1, len(removed_sequence)):
                # Not strictly increasing; sequence is not incremovable.
                if removed_sequence[index] <= removed_sequence[index - 1]:
                    is_incremovable = False
                    break

            # Increment count if subarray removal yields incremovable sequence.
            if is_incremovable:
                incremovable_subarrays_count += 1

    return incremovable_subarrays_count

Big(O) Analysis

Time Complexity

O(n^3) – The algorithm considers all possible subarrays to remove. There are approximately n^2 such subarrays (n choices for start index and n choices for end index). For each subarray removal, the algorithm constructs the remaining sequence which takes O(n) time in the worst case (if the removed subarray is small). Then, the algorithm iterates through the remaining sequence of size at most n to check if it is strictly increasing, which takes O(n) time. Since we perform the O(n) sequence construction and O(n) increasing check for each of the O(n^2) possible subarray removals, the total time complexity becomes O(n^2 * n) = O(n^3).

Space Complexity

O(N) – The brute force solution described creates a new sequence by removing a subarray from the original input array of size N. This new sequence, used to check if it's strictly increasing, takes up space proportional to the size of the original array in the worst case (when removing a very small subarray or no subarray at all). Therefore, the auxiliary space is O(N) because we create a copy of (almost) the original input of size N in each iteration to check if the remaining sequence is strictly increasing.

Optimal Solution

Approach

The goal is to find how many sections of a list can be removed so that what's left is nicely ordered. Instead of checking every possible removal, we efficiently identify good removable sections by looking at the remaining parts.

Here's how the algorithm would work step-by-step:

First, think about what it means for the remaining list to be nicely ordered: it must be non-decreasing (each number is at least as big as the one before it).
We can split the list into two parts: a beginning part and an ending part that stay. Think of each possible 'split point' between these two parts.
For each possible split point, check if the beginning part and ending part are individually nicely ordered. If not, this split isn't a candidate.
If both parts are nicely ordered, make sure that the last number in the beginning part is less than or equal to the first number in the ending part. This makes sure they can be combined into a single nicely ordered list.
If all of these checks pass, it means that the part we removed between the beginning and the end can be taken out, and what remains is nicely ordered. Increment our counter.
Repeat this process for every possible split point in the original list. The final count is the answer.

Code Implementation

def count_incremovable_subarrays(numbers):
    list_length = len(numbers)
    count = 0

    for i in range(list_length + 1):
        # Iterate through all possible split points.
        for j in range(i, list_length + 1):
            beginning_subarray = numbers[:i]
            ending_subarray = numbers[j:]

            is_beginning_sorted = all(beginning_subarray[index] <= beginning_subarray[index + 1] for index in range(len(beginning_subarray) - 1)) if len(beginning_subarray) > 1 else True
            is_ending_sorted = all(ending_subarray[index] <= ending_subarray[index + 1] for index in range(len(ending_subarray) - 1)) if len(ending_subarray) > 1 else True

            # If either subarray isn't sorted, skip this split.
            if not is_beginning_sorted or not is_ending_sorted:
                continue

            # Verify that the two subarrays can be merged into one sorted array.
            if beginning_subarray and ending_subarray and beginning_subarray[-1] > ending_subarray[0]:
                continue

            count += 1

    return count

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through all possible split points of the input array of size n. For each split point, it checks if the prefix and suffix subarrays are non-decreasing and if the last element of the prefix is less than or equal to the first element of the suffix. These checks involve iterating through the prefix and suffix, which takes O(n) time in the worst case for each split point. Since there are n possible split points, the overall time complexity is O(n * n), which simplifies to O(n²).

Space Complexity

O(1) – The provided plain English explanation focuses on iterating through the input array using split points and checking conditions. No auxiliary data structures like lists, hash maps, or significant recursion are explicitly mentioned or implied. The algorithm primarily uses a constant number of variables to track split points and perform comparisons. Therefore, the auxiliary space required is independent of the input size N (the length of the list), leading to a constant space complexity.

Edge Cases

Case	How to Handle
Empty input array	Return 0 as an empty array has no incremovable subarrays.
Array with only one element	Return 1 as an array of size one is always incremovable.
Array with two elements in increasing order	Return 3, as [], [a], [a, b] are valid subarrays if a <= b.
Array with two elements in decreasing order	Return 2, as [] and [a] are valid subarrays if a > b.
Array with all identical values	The entire array is incremovable since every subarray remains non-decreasing, calculate the number of subarrays using n*(n+1)/2 formula.
Array sorted in strictly increasing order	The entire array is incremovable, calculate the number of subarrays using n*(n+1)/2 formula.
Array sorted in strictly decreasing order	Only the empty subarray and single element subarrays are incremovable, return n+1.
Maximum sized input array (constraint: 1 <= nums.length <= 10^5)	The algorithm should be optimized to run within the time limit, ideally O(n) or O(n log n), for an array of size 10^5. Brute force will likely TLE.

Empty input array

How to Handle:

Return 0 as an empty array has no incremovable subarrays.

Array with only one element

How to Handle:

Return 1 as an array of size one is always incremovable.

Array with two elements in increasing order

How to Handle:

Return 3, as [], [a], [a, b] are valid subarrays if a <= b.

Array with two elements in decreasing order

How to Handle:

Return 2, as [] and [a] are valid subarrays if a > b.

Array with all identical values

How to Handle:

The entire array is incremovable since every subarray remains non-decreasing, calculate the number of subarrays using n*(n+1)/2 formula.

Array sorted in strictly increasing order

How to Handle:

The entire array is incremovable, calculate the number of subarrays using n*(n+1)/2 formula.

Array sorted in strictly decreasing order

How to Handle:

Only the empty subarray and single element subarrays are incremovable, return n+1.

Maximum sized input array (constraint: 1 <= nums.length <= 10^5)

How to Handle:

The algorithm should be optimized to run within the time limit, ideally O(n) or O(n log n), for an array of size 10^5. Brute force will likely TLE.