Jobs

Interviews

Discussions

Shortest Subarray to be Removed to Make Array Sorted

Medium

Asked by:

More companies

71 views

Topics:

ArraysTwo Pointers

Given an integer array arr, remove a subarray (can be empty) from arr such that the remaining elements in arr are non-decreasing.

Return the length of the shortest subarray to remove.

A subarray is a contiguous subsequence of the array.

Example 1:

Input: arr = [1,2,3,10,4,2,3,5]
Output: 3
Explanation: The shortest subarray we can remove is [10,4,2] of length 3. The remaining elements after that will be [1,2,3,3,5] which are sorted.
Another correct solution is to remove the subarray [3,10,4].

Example 2:

Input: arr = [5,4,3,2,1]
Output: 4
Explanation: Since the array is strictly decreasing, we can only keep a single element. Therefore we need to remove a subarray of length 4, either [5,4,3,2] or [4,3,2,1].

Example 3:

Input: arr = [1,2,3]
Output: 0
Explanation: The array is already non-decreasing. We do not need to remove any elements.

Constraints:

1 <= arr.length <= 10⁵
0 <= arr[i] <= 10⁹

Try coding it in LeetCode

Shortest Subarray to be Removed to Make Array Sorted

Medium

Asked by:

71 views

Topics:

ArraysTwo Pointers

Given an integer array arr, remove a subarray (can be empty) from arr such that the remaining elements in arr are non-decreasing.

Return the length of the shortest subarray to remove.

A subarray is a contiguous subsequence of the array.

Example 1:

Input: arr = [1,2,3,10,4,2,3,5]
Output: 3
Explanation: The shortest subarray we can remove is [10,4,2] of length 3. The remaining elements after that will be [1,2,3,3,5] which are sorted.
Another correct solution is to remove the subarray [3,10,4].

Example 2:

Input: arr = [5,4,3,2,1]
Output: 4
Explanation: Since the array is strictly decreasing, we can only keep a single element. Therefore we need to remove a subarray of length 4, either [5,4,3,2] or [4,3,2,1].

Example 3:

Input: arr = [1,2,3]
Output: 0
Explanation: The array is already non-decreasing. We do not need to remove any elements.

Constraints:

1 <= arr.length <= 10⁵
0 <= arr[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 is the range of values within the input array, and are negative numbers, zero, or floating-point numbers possible?
If the input array is already sorted, should I return 0, or is there another expected output?
Are duplicate values allowed in the array, and if so, how should they be handled when determining the shortest subarray to remove?
Can the input array be empty or null? If so, what should I return?
By 'sorted', do you mean strictly increasing, or is non-decreasing order (where elements can be equal) acceptable?

Brute Force Solution

Approach

The brute force approach to solving this problem involves checking every possible section of the numbers that could be removed. We'll try removing each possible section one at a time, and then see if what's left is nicely ordered.

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

First, imagine we remove nothing at all and just look at the whole list of numbers. Is it already in order?
Next, let's try removing just the first number. Is the rest of the list now in order?
Then, let's try removing the first two numbers. Is the remaining part in order?
We keep doing this, removing the first three, then four, then five, and so on until we remove all but the last number.
After that, we start again but this time we remove the second number, or the second and third numbers, or the second, third and fourth numbers, and so on.
We continue this pattern until we've tried removing every possible group of numbers from the list.
Each time we remove a group of numbers, we check if the remaining numbers are in order.
Finally, we look at all the groups we removed that left the remaining numbers in order, and we pick the smallest group.

Code Implementation

def shortest_subarray_to_be_removed_brute_force(numbers):
    number_count = len(numbers)
    shortest_removed_subarray_length = number_count

    for subarray_start in range(number_count):
        for subarray_end in range(subarray_start, number_count):
            # Determine the subarray to be removed based on the indices
            remaining_array = numbers[:subarray_start] + numbers[subarray_end+1:]

            # Check if the remaining array is sorted
            is_sorted = True
            for index in range(len(remaining_array) - 1):
                if remaining_array[index] > remaining_array[index + 1]:
                    is_sorted = False
                    break

            if is_sorted:
                #If remaining array is sorted, store the length of removed subarray
                removed_subarray_length = subarray_end - subarray_start + 1

                shortest_removed_subarray_length = min(shortest_removed_subarray_length, removed_subarray_length)

    return shortest_removed_subarray_length

Big(O) Analysis

Time Complexity

O(n^3) – The described brute force approach involves iterating through all possible subarrays to remove. For an array of size n, there are approximately n^2 possible subarrays. For each subarray removed, we need to check if the remaining array is sorted, which takes O(n) time. Therefore, the overall time complexity is O(n^2) * O(n) = O(n^3).

Space Complexity

O(1) – The brute force approach described checks if the remaining array after removing a subarray is sorted. This check is performed in-place without creating any additional data structures like temporary arrays or hash maps to store intermediate results. The algorithm uses a fixed number of variables for iteration and comparison, independent of the input array's size (N). Therefore, the auxiliary space complexity remains constant.

Optimal Solution

Approach

The goal is to find the shortest section of the list that, if removed, would leave the remaining numbers in order. We cleverly identify the longest possible ordered start and end sections and consider everything in between as the segment to remove.

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

First, find the longest ordered segment from the beginning of the list.
Then, find the longest ordered segment from the end of the list.
Now, consider different possibilities for what to remove. One possibility is to remove everything *except* the ordered segment from the beginning. Another is to remove everything *except* the ordered segment from the end.
However, it may be possible to combine these. Check if the last number in the beginning segment is less than or equal to the first number in the ending segment. If so, you can potentially combine them to create a longer overall ordered list.
Try different combinations of beginning and ending segments, always ensuring they can be combined to form an ordered list. Calculate the size of the segment to remove for each combination.
Keep track of the smallest segment to remove that you've found so far.
The smallest size you find will be the answer.

Code Implementation

def find_shortest_subarray_to_remove(input_array):
    array_length = len(input_array)
    start_index = 0
    while start_index < array_length - 1 and input_array[start_index] <= input_array[start_index + 1]:
        start_index += 1

    # If the entire array is sorted.
    if start_index == array_length - 1:
        return 0

    end_index = array_length - 1
    while end_index > 0 and input_array[end_index - 1] <= input_array[end_index]:
        end_index -= 1

    shortest_removed_subarray = min(array_length - start_index - 1, end_index)

    left_index = 0
    right_index = end_index

    # Iterate through possible start and end segment combinations.
    while left_index <= start_index and right_index < array_length:
        # If the segments can be combined to form a sorted array
        if input_array[left_index] <= input_array[right_index]:
            shortest_removed_subarray = min(shortest_removed_subarray, right_index - left_index - 1)
            left_index += 1
        else:
            # If segments cant combine, advance right segment
            right_index += 1

    return shortest_removed_subarray

Big(O) Analysis

Time Complexity

O(n^2) – Finding the longest sorted prefix and suffix takes O(n) time each. However, the core of the algorithm involves iterating through potential prefixes and suffixes to find the optimal combination. This involves comparing elements from the prefix with elements from the suffix. In the worst case, we might compare each element in the prefix with each element in the suffix, leading to a nested loop-like structure. Therefore, the time complexity is dominated by the prefix and suffix combination checks, resulting in approximately n * n comparisons, which simplifies to O(n^2).

Space Complexity

O(1) – The described algorithm primarily uses a fixed number of variables (e.g., indices to track the longest ordered segments and the minimum length to remove) regardless of the input array's size N. No auxiliary data structures like lists or hash maps are created to store intermediate results. Therefore, the space complexity remains constant, independent of the input size.

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately as an empty array is already sorted.
Array with 1 or 2 elements	If the array has 1 element, return 0; if 2 elements, return 0 if sorted, 1 otherwise.
Array is already sorted in ascending order	Return 0, as no subarray needs to be removed.
Array is sorted in descending order	Return array length - 1, as removing all but one element will sort it.
Array with all identical elements	Return 0, as the array is already sorted.
Array with large numbers at the beginning followed by small numbers	The algorithm should correctly identify and remove the initial large subarray.
Array with a small unsorted subarray in the middle	The algorithm must accurately pinpoint the beginning and end of this unsorted section to minimize the removal.
Integer overflow if calculating lengths of subarrays	Use data types that can accommodate large array lengths to prevent overflow issues during length calculations.

Null or empty input array

How to Handle:

Return 0 immediately as an empty array is already sorted.

Array with 1 or 2 elements

How to Handle:

If the array has 1 element, return 0; if 2 elements, return 0 if sorted, 1 otherwise.

Array is already sorted in ascending order

How to Handle:

Return 0, as no subarray needs to be removed.

Array is sorted in descending order

How to Handle:

Return array length - 1, as removing all but one element will sort it.

Array with all identical elements

How to Handle:

Return 0, as the array is already sorted.

Array with large numbers at the beginning followed by small numbers

How to Handle:

The algorithm should correctly identify and remove the initial large subarray.

Array with a small unsorted subarray in the middle

How to Handle:

The algorithm must accurately pinpoint the beginning and end of this unsorted section to minimize the removal.

Integer overflow if calculating lengths of subarrays

How to Handle:

Use data types that can accommodate large array lengths to prevent overflow issues during length calculations.

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 is the range of values within the input array, and are negative numbers, zero, or floating-point numbers possible?
If the input array is already sorted, should I return 0, or is there another expected output?
Are duplicate values allowed in the array, and if so, how should they be handled when determining the shortest subarray to remove?
Can the input array be empty or null? If so, what should I return?
By 'sorted', do you mean strictly increasing, or is non-decreasing order (where elements can be equal) acceptable?

Brute Force Solution

Approach

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

First, imagine we remove nothing at all and just look at the whole list of numbers. Is it already in order?
Next, let's try removing just the first number. Is the rest of the list now in order?
Then, let's try removing the first two numbers. Is the remaining part in order?
We keep doing this, removing the first three, then four, then five, and so on until we remove all but the last number.
After that, we start again but this time we remove the second number, or the second and third numbers, or the second, third and fourth numbers, and so on.
We continue this pattern until we've tried removing every possible group of numbers from the list.
Each time we remove a group of numbers, we check if the remaining numbers are in order.
Finally, we look at all the groups we removed that left the remaining numbers in order, and we pick the smallest group.

Code Implementation

def shortest_subarray_to_be_removed_brute_force(numbers):
    number_count = len(numbers)
    shortest_removed_subarray_length = number_count

    for subarray_start in range(number_count):
        for subarray_end in range(subarray_start, number_count):
            # Determine the subarray to be removed based on the indices
            remaining_array = numbers[:subarray_start] + numbers[subarray_end+1:]

            # Check if the remaining array is sorted
            is_sorted = True
            for index in range(len(remaining_array) - 1):
                if remaining_array[index] > remaining_array[index + 1]:
                    is_sorted = False
                    break

            if is_sorted:
                #If remaining array is sorted, store the length of removed subarray
                removed_subarray_length = subarray_end - subarray_start + 1

                shortest_removed_subarray_length = min(shortest_removed_subarray_length, removed_subarray_length)

    return shortest_removed_subarray_length

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, find the longest ordered segment from the beginning of the list.
Then, find the longest ordered segment from the end of the list.
Now, consider different possibilities for what to remove. One possibility is to remove everything *except* the ordered segment from the beginning. Another is to remove everything *except* the ordered segment from the end.
However, it may be possible to combine these. Check if the last number in the beginning segment is less than or equal to the first number in the ending segment. If so, you can potentially combine them to create a longer overall ordered list.
Try different combinations of beginning and ending segments, always ensuring they can be combined to form an ordered list. Calculate the size of the segment to remove for each combination.
Keep track of the smallest segment to remove that you've found so far.
The smallest size you find will be the answer.

Code Implementation

def find_shortest_subarray_to_remove(input_array):
    array_length = len(input_array)
    start_index = 0
    while start_index < array_length - 1 and input_array[start_index] <= input_array[start_index + 1]:
        start_index += 1

    # If the entire array is sorted.
    if start_index == array_length - 1:
        return 0

    end_index = array_length - 1
    while end_index > 0 and input_array[end_index - 1] <= input_array[end_index]:
        end_index -= 1

    shortest_removed_subarray = min(array_length - start_index - 1, end_index)

    left_index = 0
    right_index = end_index

    # Iterate through possible start and end segment combinations.
    while left_index <= start_index and right_index < array_length:
        # If the segments can be combined to form a sorted array
        if input_array[left_index] <= input_array[right_index]:
            shortest_removed_subarray = min(shortest_removed_subarray, right_index - left_index - 1)
            left_index += 1
        else:
            # If segments cant combine, advance right segment
            right_index += 1

    return shortest_removed_subarray

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately as an empty array is already sorted.
Array with 1 or 2 elements	If the array has 1 element, return 0; if 2 elements, return 0 if sorted, 1 otherwise.
Array is already sorted in ascending order	Return 0, as no subarray needs to be removed.
Array is sorted in descending order	Return array length - 1, as removing all but one element will sort it.
Array with all identical elements	Return 0, as the array is already sorted.
Array with large numbers at the beginning followed by small numbers	The algorithm should correctly identify and remove the initial large subarray.
Array with a small unsorted subarray in the middle	The algorithm must accurately pinpoint the beginning and end of this unsorted section to minimize the removal.
Integer overflow if calculating lengths of subarrays	Use data types that can accommodate large array lengths to prevent overflow issues during length calculations.

Null or empty input array

How to Handle:

Return 0 immediately as an empty array is already sorted.

Array with 1 or 2 elements

How to Handle:

If the array has 1 element, return 0; if 2 elements, return 0 if sorted, 1 otherwise.

Array is already sorted in ascending order

How to Handle:

Return 0, as no subarray needs to be removed.

Array is sorted in descending order

How to Handle:

Return array length - 1, as removing all but one element will sort it.

Array with all identical elements

How to Handle:

Return 0, as the array is already sorted.

Array with large numbers at the beginning followed by small numbers

How to Handle:

The algorithm should correctly identify and remove the initial large subarray.

Array with a small unsorted subarray in the middle

How to Handle:

The algorithm must accurately pinpoint the beginning and end of this unsorted section to minimize the removal.

Integer overflow if calculating lengths of subarrays

How to Handle:

Use data types that can accommodate large array lengths to prevent overflow issues during length calculations.