1574. Shortest Subarray to be Removed to Make Array Sorted

Given an array of integers, the task is to find the length of the shortest subarray that can be removed to make the remaining array sorted in non-decreasing order. The array can contain duplicates, and the result should be the smallest number of elements that need to be removed.

To implement a solution, we need to divide the array into two parts: a prefix that is sorted and a suffix that is sorted. The main idea is to find the maximum 'middle' section (between these two parts) that can be removed such that the resulting array is still sorted. This can be achieved in the following steps:

1. Identify the longest non-decreasing prefix.
2. Identify the longest non-decreasing suffix.
3. Try to remove the middle part or some overlapping part between the prefix and suffix to minimize the number of elements removed.
4. Compare indices from prefix and suffix to find the merging point, ensuring the values do not break the sorted order.

The time complexity is O(n) as we only make one linear pass over the array to determine the prefix and suffix, and an additional linear comparison to find the best merging point. The space complexity is O(1) as we are not using any extra space beyond a few variables.

Consider the array = [1, 2, 3, 10, 4, 2, 3, 5]:

• The longest non-decreasing prefix is [1, 2, 3] (indices 0 to 2).
• The longest non-decreasing suffix is [2, 3, 5] (indices 5 to 7).
• By removing the middle section from indices 3 to 4 ([10, 4]), the resulting array [1, 2, 3, 2, 3, 5] is sorted.

This problem is related to array manipulation and greedy algorithms. No specific framework is used, but it involves understanding the array structure:

• Greedy Algorithms - Wikipedia

We start by implementing the structure of the solution with placeholder return value to allow for user development.

2024-11-15 Shortest Subarray to be Removed to Make Array Sorted - Submission Detail - LeetCode leetcode.com

/**
 * @param {number[]} arr - The input array of integers.
 * @returns {number} The length of the shortest subarray to be removed.
 */
function shortestSubarrayToRemove(arr) {
    const log = typeof NestedInteger !== 'undefined' ? () => {} : console.log;

    if (arr.length < 2) {
        return 0;
    }

    let begin = 0;
    let end = arr.length - 1;

    while (begin < arr.length - 1 && arr[begin] <= arr[begin + 1]) {
        begin += 1;
    }

    if (begin === arr.length - 1) {
        return 0;
    }

    while (end > 0 && arr[end - 1] <= arr[end]) {
        end -= 1;
    }

    let minToRemove = Math.min(arr.length - begin - 1, end);

    let i = 0;
    let j = end;

    while (i <= begin && j < arr.length) {
        if (arr[i] <= arr[j]) {
            minToRemove = Math.min(minToRemove, j - i - 1);
            i += 1;
        } else {
            j += 1;
        }
    }

    return minToRemove;
}

// Test cases
const testCases = [
    { arr: [1, 2, 3, 10, 4, 2, 3, 5], expected: 3 },
    { arr: [5, 1, 2, 3, 4], expected: 1 },
    { arr: [1, 2, 3], expected: 0 },
    { arr: [1], expected: 0 }, // Single element
    { arr: [7, 6, 5, 4], expected: 3 }, // Fully descending
];

testCases.forEach((test, index) => {
    const result = shortestSubarrayToRemove(test.arr);
    console.log(`Test Case ${index + 1}: ${result === test.expected ? 'Passed' : '\x1bFailed'} (Expected: ${test.expected}, Got: ${result})`);
});

: Test Case 1: Passed (Expected: 3, Got: 3)
: Test Case 2: Passed (Expected: 1, Got: 1)
: Test Case 3: Passed (Expected: 0, Got: 0)
: Test Case 4: Passed (Expected: 0, Got: 0)
: Test Case 5: Passed (Expected: 3, Got: 3)
: undefined

This skeleton provides a starting point. Upon completion, you should replace the placeholder return with your implementation logic. Test cases are provided to ensure comprehensive coverage.