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 I

Number: 3252

Difficulty: Easy

Paid? No

Companies: Apple

Problem Description

Given a 0-indexed array of positive integers nums, a subarray (a contiguous non-empty sequence) is called incremovable if, after removing that subarray from nums, the remaining elements (in order) form a strictly increasing sequence. (An empty array is considered strictly increasing.) Return the total number of such incremovable subarrays.

Key Insights

  • Removing a subarray splits the array into two parts: left (from start to i-1) and right (from j+1 to end) for a removed subarray nums[i...j].
  • For the remaining array to be strictly increasing:
    • The left part (if non-empty) must be strictly increasing.
    • The right part (if non-empty) must be strictly increasing.
    • If both parts exist, the last element of the left part must be less than the first element of the right part.
  • Precompute whether every prefix and suffix of nums is strictly increasing. Then enumerate over all possible subarrays and check if removing that subarray meets the criteria.
  • The whole array removal is allowed because an empty array is considered strictly increasing.

Space and Time Complexity

Time Complexity: O(n²), since we check every possible subarray and each check occurs in O(1) with precomputation; n is at most 50. Space Complexity: O(n), for storing prefix and suffix booleans.

Solution

We first precompute two arrays:

  1. prefixStrict: prefixStrict[i] is true if the subarray nums[0...i] is strictly increasing.
  2. suffixStrict: suffixStrict[i] is true if the subarray nums[i...n-1] is strictly increasing.

For each subarray nums[i...j]:

  • The left part (if i > 0) must satisfy prefixStrict[i-1].
  • The right part (if j < n-1) must satisfy suffixStrict[j+1].
  • Additionally, if both parts exist (i > 0 and j < n-1), we require nums[i-1] < nums[j+1].

We then count all subarrays for which these conditions hold. The algorithm is O(n²) which is acceptable given the constraints.

Code Solutions

# Python solution with line-by-line comments
def countIncremovableSubarrays(nums):
    n = len(nums)
    # Precompute prefixStrict: True if nums[0...i] is strictly increasing
    prefixStrict = [True] * n
    for i in range(1, n):
        prefixStrict[i] = prefixStrict[i-1] and (nums[i-1] < nums[i])
    
    # Precompute suffixStrict: True if nums[i...n-1] is strictly increasing
    suffixStrict = [True] * n
    for i in range(n-2, -1, -1):
        suffixStrict[i] = suffixStrict[i+1] and (nums[i] < nums[i+1])
    
    count = 0
    # Enumerate all possible subarrays to remove: from index i to j
    for i in range(0, n):
        for j in range(i, n):
            valid = True
            # Check left part: if exists, must be strictly increasing
            if i > 0:
                valid = valid and prefixStrict[i-1]
            # Check right part: if exists, must be strictly increasing
            if j < n-1:
                valid = valid and suffixStrict[j+1]
            # If both left and right parts exist, they must connect strictly.
            if i > 0 and j < n-1:
                valid = valid and (nums[i-1] < nums[j+1])
            
            if valid:
                count += 1
    return count

# 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