1574. Shortest Subarray to be Removed to Make Array Sorted Medium

1/**
2 * [1574] Shortest Subarray to be Removed to Make Array Sorted
3 *
4 * Given an integer array arr, remove a subarray (can be empty) from arr such that the remaining elements in arr are non-decreasing.
5 * Return the length of the shortest subarray to remove.
6 * A subarray is a contiguous subsequence of the array.
7 *  
8 * Example 1:
9 * 
10 * Input: arr = [1,2,3,10,4,2,3,5]
11 * Output: 3
12 * 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.
13 * Another correct solution is to remove the subarray [3,10,4].
14 * 
15 * Example 2:
16 * 
17 * Input: arr = [5,4,3,2,1]
18 * Output: 4
19 * 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].
20 * 
21 * Example 3:
22 * 
23 * Input: arr = [1,2,3]
24 * Output: 0
25 * Explanation: The array is already non-decreasing. We do not need to remove any elements.
26 * 
27 *  
28 * Constraints:
29 * 
30 * 	1 <= arr.length <= 10^5
31 * 	0 <= arr[i] <= 10^9
32 * 
33 */
34pub struct Solution {}
35
36// problem: https://leetcode.com/problems/shortest-subarray-to-be-removed-to-make-array-sorted/
37// discuss: https://leetcode.com/problems/shortest-subarray-to-be-removed-to-make-array-sorted/discuss/?currentPage=1&orderBy=most_votes&query=
38
39// submission codes start here
40
41impl Solution {
42    pub fn find_length_of_shortest_subarray(arr: Vec<i32>) -> i32 {
43        0
44    }
45}
46
47// submission codes end
48
49#[cfg(test)]
50mod tests {
51    use super::*;
52
53    #[test]
54    fn test_1574() {
55    }
56}
57