leetcode

Leetcode problem solutions
git clone https://git.sinitax.com/sinitax/leetcode
Log | Files | Refs | sfeed.txt

1574-shortest-subarray-to-be-removed-to-make-array-sorted.rs (2661B)

      1/// 1574. Shortest Subarray to be Removed to Make Array Sorted (Medium)
      2///
      3/// Given an integer array arr, remove a subarray (can be empty) from arr such
      4/// that the remaining elements in arr are *non-decreasing*.
      5///
      6/// Return the length of the shortest subarray to remove.
      7///
      8/// A *subarray* is a contiguous subsequence of the array.
      9///
     10/// *Example 1:*
     11///
     12///   *Input:* arr = [1,2,3,10,4,2,3,5]
     13///   *Output:* 3
     14///   *Explanation:* The shortest subarray we can remove is [10,4,2] of length 3.
     15///   The remaining elements after that will be [1,2,3,3,5] which are sorted.
     16///   Another correct solution is to remove the subarray [3,10,4].
     17///
     18/// *Example 2:*
     19///
     20///   *Input:* arr = [5,4,3,2,1]
     21///   *Output:* 4
     22///   *Explanation:* Since the array is strictly decreasing, we can only keep a
     23///   single element. Therefore we need to remove a subarray of length 4, either
     24///   [5,4,3,2] or [4,3,2,1].
     25///
     26/// *Example 3:*
     27///
     28///   *Input:* arr = [1,2,3]
     29///   *Output:* 0
     30///   *Explanation:* The array is already non-decreasing. We do not need to remove
     31///   any elements.
     32///
     33/// *Constraints:*
     34///
     35///   * 1 <= arr.length <= 105
     36///   * 0 <= arr[i] <= 109
     37///
     38use leetcode::*;
     39use std::cmp;
     40
     41struct Solution {}
     42
     43impl Solution {
     44    pub fn find_length_of_shortest_subarray(arr: Vec<i32>) -> i32 {
     45        let n = arr.len();
     46        if n == 0 {
     47            return 0;
     48        }
     49        let mut left = 1usize;
     50        while left < n && arr[left] >= arr[left - 1] {
     51            left += 1;
     52        }
     53        let mut right = 1usize;
     54        while right < n && arr[n - 1 - right] <= arr[n - right] {
     55            right += 1;
     56        }
     57        let mut best = cmp::min(n - left, n - right);
     58        let mut end = n - right;
     59        let mut high = arr[end];
     60        for start in 0..left {
     61            let low = arr[start];
     62            while high < low && end < n {
     63                end += 1;
     64                if end < n {
     65                    high = arr[end];
     66                }
     67            }
     68            best = cmp::min(best, cmp::max(end - start, 1) - 1);
     69        }
     70        best as i32
     71    }
     72}
     73
     74pub fn main() {
     75    println!(
     76        "{:?}",
     77        Solution::find_length_of_shortest_subarray(arg_into(1))
     78    );
     79}
     80
     81#[cfg(test)]
     82mod tests {
     83    use crate::Solution;
     84    use leetcode::vi;
     85
     86    #[test]
     87    fn test() {
     88        assert_eq!(
     89            Solution::find_length_of_shortest_subarray(vi("[1,2,3,10,4,2,3,5]")),
     90            3
     91        );
     92        assert_eq!(
     93            Solution::find_length_of_shortest_subarray(vi("[5,4,3,2,1]")),
     94            4
     95        );
     96        assert_eq!(Solution::find_length_of_shortest_subarray(vi("[1,2,3]")), 0);
     97    }
     98}