1
class Solution {
2
 public:
3
  int max_value = 1000000;
4
  int min_value = -1000000;
5

6
  int findUnsortedSubarray(vector<int> &nums) {
7
    // max_list refers to: the max value on the left side of the current element
8
    // min_list refers to: the min value on the right side of the current
9
    // element
10
    vector<int> max_list(nums.size(), 0);
11
    vector<int> min_list(nums.size(), 0);
12
    min_list[nums.size() - 1] = max_value;
13
    max_list[0] = min_value;
14

15
    // init two lists
16
    for (int i = nums.size() - 2; i >= 0; i--) min_list[i] = min(min_list[i + 1], nums[i + 1]);
17

18
    for (int i = 1; i < nums.size(); i++) max_list[i] = max(max_list[i - 1], nums[i - 1]);
19

20
    // get left bound
21
    int left = 0;
22
    while (left < nums.size() && min_list[left] >= nums[left]) left++;
23

24
    // get right bound
25
    int right = nums.size() - 1;
26
    while (right >= 0 && max_list[right] <= nums[right]) right--;
27

28
    if (left == nums.size()) // monotonic ascending array
29
      return 0;
30
    else
31
      return (right - left + 1);
32
  }
33
};