Problem Description

You are given an integer array arr. Your task is to remove a subarray (which can be empty) from arr such that the remaining elements form a non-decreasing sequence.

A non-decreasing sequence means each element is less than or equal to the next element (i.e., arr[i] <= arr[i+1]).

A subarray is a contiguous portion of the array - meaning you can only remove elements that are next to each other, not individual elements from different positions.

Your goal is to find the minimum length of the subarray that needs to be removed to make the remaining array non-decreasing.

For example:

• If arr = [1, 2, 3, 10, 4, 2, 3, 5], you could remove the subarray [10, 4, 2] (length 3) to get [1, 2, 3, 3, 5], which is non-decreasing.
• If the array is already non-decreasing like [1, 2, 3, 4, 5], you don't need to remove anything, so return 0.

The key insight is that after removing a subarray, you're essentially keeping a prefix and a suffix of the original array, and these must combine to form a non-decreasing sequence.

Intuition

When we remove a subarray from the middle, we're essentially keeping a prefix (left part) and a suffix (right part) of the original array. For the remaining array to be non-decreasing, two conditions must hold:

1. The prefix itself must be non-decreasing
2. The suffix itself must be non-decreasing
3. The last element of the prefix must be ≤ the first element of the suffix

This observation leads us to think: what if we first identify the longest non-decreasing prefix and the longest non-decreasing suffix?

Let's say the longest non-decreasing prefix ends at index i, and the longest non-decreasing suffix starts at index j.

If i >= j, it means these two parts overlap or touch each other - the entire array is already non-decreasing! We need to remove nothing, so return 0.

Otherwise, we have three strategies:

1. Keep only the prefix: remove everything after index i, which removes n - i - 1 elements
2. Keep only the suffix: remove everything before index j, which removes j elements
3. Keep both a prefix and a suffix: we need to ensure they can connect properly

For strategy 3, we can iterate through each possible endpoint of the prefix (from index 0 to i). For each prefix ending at index l, we need to find where in the suffix we can connect. Since the suffix arr[j..n-1] is non-decreasing, we can use binary search to find the first position r in the suffix where arr[r] >= arr[l]. Then we remove everything between l and r, which is r - l - 1 elements.

The minimum among all these possibilities gives us our answer.

Learn more about Stack, Two Pointers, Binary Search and Monotonic Stack patterns.

Solution Approach

The implementation follows a two-pointer approach combined with binary search:

Step 1: Find the longest non-decreasing prefix

i = 0
while i + 1 < n and arr[i] <= arr[i + 1]:
    i += 1

We iterate from the beginning and stop when we find the first position where arr[i] > arr[i + 1]. The prefix arr[0..i] is non-decreasing.

Step 2: Find the longest non-decreasing suffix

j = n - 1
while j - 1 >= 0 and arr[j - 1] <= arr[j]:
    j -= 1

We iterate from the end and stop when we find the first position where arr[j - 1] > arr[j]. The suffix arr[j..n-1] is non-decreasing.

Step 3: Check if array is already non-decreasing

if i >= j:
    return 0

If the prefix and suffix overlap or meet, the entire array is non-decreasing.

Step 4: Initialize answer with simple cases

ans = min(n - i - 1, j)

• n - i - 1: Remove everything after the prefix (keep only prefix)
• j: Remove everything before the suffix (keep only suffix)

Step 5: Try combining prefix and suffix

for l in range(i + 1):
    r = bisect_left(arr, arr[l], lo=j)
    ans = min(ans, r - l - 1)

For each possible prefix ending at index l:

• Use binary search (bisect_left) to find the first position r in the suffix arr[j..n-1] where arr[r] >= arr[l]
• The lo=j parameter ensures we only search within the suffix portion
• Calculate the length of subarray to remove: r - l - 1 (everything between l and r)
• Update the minimum answer

The algorithm efficiently explores all valid ways to remove a contiguous subarray, ensuring the remaining parts form a non-decreasing sequence. The time complexity is O(n log n) due to the binary search performed for each prefix position.

Example Walkthrough

Let's walk through the algorithm with arr = [1, 2, 3, 10, 4, 2, 3, 5].

Step 1: Find longest non-decreasing prefix

• Start at index 0: 1 <= 2 ✓, continue
• Index 1: 2 <= 3 ✓, continue
• Index 2: 3 <= 10 ✓, continue
• Index 3: 10 <= 4 ✗, stop

The longest non-decreasing prefix is [1, 2, 3, 10], ending at i = 3.

Step 2: Find longest non-decreasing suffix

• Start at index 7: 3 <= 5 ✓, continue
• Index 6: 2 <= 3 ✓, continue
• Index 5: 4 <= 2 ✗, stop

The longest non-decreasing suffix is [2, 3, 5], starting at j = 5.

Step 3: Check if already non-decreasing

• Is i >= j? Is 3 >= 5? No, so we continue.

Step 4: Initialize with simple cases

• Keep only prefix: remove indices 4-7, length = 8 - 3 - 1 = 4
• Keep only suffix: remove indices 0-4, length = 5
• Initial ans = min(4, 5) = 4

Step 5: Try combining prefix and suffix

For each prefix ending position l from 0 to 3:

• l = 0 (prefix = [1]):

  • Binary search in suffix [2, 3, 5] for first element ≥ 1
  • Found at index 5 (value = 2)
  • Remove indices 1-4, length = 5 - 0 - 1 = 4
  • ans = min(4, 4) = 4

• l = 1 (prefix = [1, 2]):

  • Binary search in suffix [2, 3, 5] for first element ≥ 2
  • Found at index 5 (value = 2)
  • Remove indices 2-4, length = 5 - 1 - 1 = 3
  • ans = min(4, 3) = 3

• l = 2 (prefix = [1, 2, 3]):

  • Binary search in suffix [2, 3, 5] for first element ≥ 3
  • Found at index 6 (value = 3)
  • Remove indices 3-5, length = 6 - 2 - 1 = 3
  • ans = min(3, 3) = 3

• l = 3 (prefix = [1, 2, 3, 10]):

  • Binary search in suffix [2, 3, 5] for first element ≥ 10
  • Not found (returns index 8, beyond array)
  • Remove indices 4-7, length = 8 - 3 - 1 = 4
  • ans = min(3, 4) = 3

Final answer: 3

The optimal solution removes the subarray [10, 4, 2] at indices 3-5, leaving [1, 2, 3, 3, 5] which is non-decreasing.

Solution Implementation

Time and Space Complexity

The time complexity is O(n log n), where n is the length of the array. This complexity comes from:

• The first while loop runs at most n times to find the longest non-decreasing prefix: O(n)
• The second while loop runs at most n times to find the longest non-decreasing suffix: O(n)
• The for loop iterates through at most i + 1 elements (which is at most n): O(n)
• Inside the for loop, bisect_left performs binary search on the suffix portion of the array, which takes O(log n) time
• Therefore, the overall time complexity is O(n) + O(n) + O(n × log n) = O(n log n)

The space complexity is O(1) as the algorithm only uses a constant amount of extra space for variables i, j, l, r, ans, and n, regardless of the input size.

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

Common Pitfalls

Pitfall 1: Incorrect Binary Search Usage for Finding Valid Suffix Connection

The Problem: Using bisect_left(arr, arr[prefix_idx], lo=right_start) doesn't guarantee a valid connection between prefix and suffix. The binary search finds where arr[prefix_idx] would fit in the sorted suffix, but it doesn't verify that the value at that position actually exists or forms a valid non-decreasing connection.

Why It Happens:

• bisect_left returns an insertion point, which could be n (beyond array bounds)
• Even if the index is valid, we need arr[suffix_idx] >= arr[prefix_idx] for a valid connection
• The suffix starting at right_start is non-decreasing, but we need to ensure the connection point exists

Correct Solution:

for prefix_idx in range(left_end + 1):
    # Use binary search to find insertion point
    suffix_idx = bisect_left(arr, arr[prefix_idx], lo=right_start)
  
    # Ensure suffix_idx is within bounds
    if suffix_idx < n:
        # Valid connection exists
        removal_length = suffix_idx - prefix_idx - 1
        min_removal = min(min_removal, removal_length)

Pitfall 2: Off-by-One Error in Removal Length Calculation

The Problem: Confusion about what indices represent (inclusive vs exclusive) leads to incorrect removal length calculations.

Why It Happens:

• left_end is the last index of the valid prefix (inclusive)
• right_start is the first index of the valid suffix (inclusive)
• When calculating removal length between prefix_idx and suffix_idx, it's easy to miscount

Correct Understanding:

• If keeping prefix up to index i and suffix from index j, we remove indices [i+1, j-1]
• Removal length = j - i - 1 = (j-1) - (i+1) + 1
• Example: If i=2 and j=5, we keep [0,1,2] and [5,...], removing [3,4] (length 2)

Pitfall 3: Not Handling Edge Cases Properly

The Problem: Missing edge cases like single-element arrays or arrays with all equal elements.

Why It Happens:

• The algorithm assumes there are distinct increasing/decreasing patterns
• Equal consecutive elements need special consideration for "non-decreasing" vs "strictly increasing"

Correct Solution: Ensure the comparison uses <= (not <) for non-decreasing sequences:

# Correct: non-decreasing allows equal elements
while left_end + 1 < n and arr[left_end] <= arr[left_end + 1]:
    left_end += 1

# Incorrect: would stop at equal elements
while left_end + 1 < n and arr[left_end] < arr[left_end + 1]:
    left_end += 1