leetcode

Leetcode Solutions (0x6A73)
git clone https://git.pngu.org/leetcode
Log | Files | Refs | Submodules | README

shortest_subarr_remove_sort.c (1228B)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 1574. Shortest Subarray to be Removed to Make Array Sorted
#include "leetcode.h"

/*
 * 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.
 */

int findLengthOfShortestSubarray(int *arr, int arrSize) {
  int left = 0, right = arrSize - 1;
  while (left + 1 < arrSize && arr[left] <= arr[left + 1])
    left++;
  if (left == arrSize - 1)
    return 0;
  while (right > left && arr[right - 1] <= arr[right])
    right--;
  int ans = arrSize - left - 1 < right ? arrSize - left - 1 : right;
  int i = 0, j = right;
  while (i <= left && j < arrSize) {
    if (arr[j] >= arr[i]) {
      ans = ans < j - i - 1 ? ans : j - i - 1;
      i++;
    } else
      j++;
  }
  return ans;
}

int main() {
  int a1[] = {1, 2, 3, 10, 4, 2, 3, 5}, a2[] = {5, 4, 3, 2, 1},
      a3[] = {1, 2, 3};
  printf("%d\n", findLengthOfShortestSubarray(a1, ARRAY_SIZE(a1))); // expect: 3
  printf("%d\n", findLengthOfShortestSubarray(a2, ARRAY_SIZE(a2))); // expect: 4
  printf("%d\n", findLengthOfShortestSubarray(a3, ARRAY_SIZE(a3))); // expect: 0
}