We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count the Number of Incremovable Subarrays II

Number: 3248

Difficulty: Hard

Paid? No

Companies: DE Shaw, Apple

Problem Description

Given a 0-indexed array of positive integers, count the number of non‐empty contiguous subarrays (called “incremovable”) that, when removed from the array, leave the remaining elements (in order) forming a strictly increasing sequence. (Note that an empty array is considered strictly increasing.)

For example, in the array [5,3,4,6,7] removing the subarray [3,4] yields [5,6,7] which is strictly increasing.

Key Insights

  • Removing a subarray divides the array into a left part (before removal) and a right part (after removal). Both parts, taken alone, must be strictly increasing.
  • When both parts are non-empty, an extra “bridge condition” is required: the last element of the left part must be less than the first element of the right part.
  • Precomputing whether each prefix (from index 0 up to i) and each suffix (from index i to end) is strictly increasing helps quickly decide if the remaining segments are good.
  • The challenge is to count in O(n log n) or O(n) time without explicitly iterating over every O(n²) subarray.
  • One strategy is to treat removals in three cases: removals that remove a prefix (no left part), removals that remove a suffix (no right part) and removals “in the middle” (both parts exist). For the middle removals, binary search over candidate indices (using precomputed “suffix valid” indices) can help enforce the bridge condition.

Space and Time Complexity

Time Complexity: O(n log n) – n for scanning the array plus up to O(n log n) from binary searches. Space Complexity: O(n) – to store prefix and suffix validity arrays (and an auxiliary list for binary search).

Solution

The key idea is to note that if you remove the subarray nums[i…j], the remaining array becomes the concatenation of left = nums[0…i-1] and right = nums[j+1…n-1]. For the result to be strictly increasing: • If the left part exists (i > 0), then nums[0 … i-1] must be strictly increasing. • If the right part exists (j < n-1), then nums[j+1 … n-1] must be strictly increasing. • And if both parts exist, nums[i-1] must be strictly less than nums[j+1].

To efficiently count valid removals:

  1. Precompute two boolean arrays: one for prefix validity (is the subarray nums[0 … i] strictly increasing?) and one for suffix validity (is the subarray nums[i … n-1] strictly increasing?).
  2. Count removals in three separate cases:
    • Case A: Removing a prefix (i == 0). In this case no left part exists so we only require that the right part (if non-empty) is strictly increasing.
    • Case B: Removing a suffix (j == n-1). Here no right part exists so only the left part needs to be strictly increasing.
    • Case C: Removing a subarray in the middle (i > 0 and j < n-1). In addition to the left and right parts being individually strictly increasing, the boundary condition nums[i-1] < nums[j+1] must hold.
  3. For Case C, we iterate over valid starting indices (i from 1 to n-1 for which prefix ending at i–1 is strictly increasing) and use binary search (on a precollected list of indices from the right part with valid suffix property) to quickly count the number of j values (with j >= i and j < n-1) that satisfy both the right part validity and the bridge condition.

Finally, add the counts from all three cases. Special attention is needed to avoid double counting removals that are both prefix and suffix removals (i.e. removing the entire array).

Code Solutions

# Python solution with line-by-line comments
import bisect

def countIncremovableSubarrays(nums):
    n = len(nums)
    
    # Precompute prefix validity: prefix_valid[i] is True if nums[0..i] is strictly increasing.
    prefix_valid = [True] * n
    for i in range(1, n):
        prefix_valid[i] = prefix_valid[i-1] and (nums[i-1] < nums[i])
    
    # Precompute suffix validity: suffix_valid[i] is True if nums[i..n-1] is strictly increasing.
    suffix_valid = [True] * n
    for i in range(n-2, -1, -1):
        suffix_valid[i] = suffix_valid[i+1] and (nums[i] < nums[i+1])
        
    result = 0
    
    # Case A: removal is a prefix, i == 0.
    # For any j from 0 to n-1, if right part (nums[j+1..n-1]) is valid (or j == n-1, corresponding to empty right),
    # then removal (0, j) is valid.
    for j in range(n):
        if j == n-1 or suffix_valid[j+1]:
            result += 1
            
    # Case B: removal is a suffix, j == n-1.
    # For any i from 1 to n-1, if left part (nums[0..i-1]) is valid, then removal (i, n-1) is valid.
    # (Note: (0, n-1) is already counted in Case A.)
    for i in range(1, n):
        if prefix_valid[i-1]:
            result += 1

    # Case C: removal is in the middle (i > 0 and j < n-1).
    # For these, we require:
    #   1. Left part (nums[0..i-1]) is strictly increasing (i.e. prefix_valid[i-1] is True).
    #   2. Right part (nums[j+1..n-1]) is strictly increasing (i.e. suffix_valid[j+1] is True).
    #   3. Bridge condition: nums[i-1] < nums[j+1].
    # To count these quickly, we precompute a list of indices p for which suffix_valid[p] is True.
    # Here, for a given j (< n-1), we view p = j+1.
    valid_suffix_indices = [i for i in range(n) if suffix_valid[i]]
    
    # For each possible starting index i (i > 0) that yields a valid left part:
    for i in range(1, n):
        if not prefix_valid[i-1]:
            continue  # skip if left part is not strictly increasing
        left_last = nums[i-1]
        # In the remaining array, j+1 (denoted by p) must be greater than left_last.
        # Also, since j >= i, we need p = j+1 >= i+1.
        lower_bound = max(i+1, 0)
        # Binary search in valid_suffix_indices for the first index where:
        # index >= lower_bound and nums[index] > left_last.
        idx = bisect.bisect_left(valid_suffix_indices, lower_bound)
        count = 0
        # Iterate all valid suffix indices starting from idx meeting the bridge condition.
        while idx < len(valid_suffix_indices) and valid_suffix_indices[idx] < n:
            p = valid_suffix_indices[idx]
            if nums[p] > left_last:
                # p = j+1 so j = p - 1.
                # Also ensure that j < n-1, i.e. p <= n-1.
                if p <= n-1:
                    # But note: j = p - 1 must also be >= i.
                    if p - 1 >= i:
                        count += 1
            idx += 1
        result += count

    return result

# Example usage:
print(countIncremovableSubarrays([1,2,3,4]))   # Expected output: 10
print(countIncremovableSubarrays([6,5,7,8]))     # Expected output: 7
print(countIncremovableSubarrays([8,7,6,6]))     # Expected output: 3
← Back to All Questions