# 0581. Shortest Unsorted Continuous Subarray

https://leetcode.com/problems/shortest-unsorted-continuous-subarray

## Description

Given an integer array `nums`, you need to find one **continuous subarray** that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order.

Return _the shortest such subarray and output its length_.

**Example 1:**

```
**Input:** nums = [2,6,4,8,10,9,15]
**Output:** 5
**Explanation:** You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.
```

**Example 2:**

```
**Input:** nums = [1,2,3,4]
**Output:** 0
```

**Example 3:**

```
**Input:** nums = [1]
**Output:** 0
```

**Constraints:**

* `1 <= nums.length <= 104`
* `-105 <= nums[i] <= 105`

**Follow up:** Can you solve it in `O(n)` time complexity?

## ac1: stack with 2 passes

Learnt: for array, think about two pass: from left and from right.

```java
class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int left = nums.length, right = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
                int idx = stack.pop();
                left = Math.min(left, idx);
            }
            stack.push(i);
        }
        
        stack = new ArrayDeque<>();
        for (int i = nums.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
                int idx = stack.pop();
                right = Math.max(right, idx);
            }
            stack.push(i);
        }
        
        return Math.max(0, right - left + 1);
    }
}

// O(N) time, O(N) space
// To find left and right bound.
```

## ac2: similar idea without stack

We don't really need a stack to find the left/right boundary.

```java
class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int left = nums.length, right = 0;
        
        // 1st pass from left
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            max = Math.max(max, nums[i]);
            if (nums[i] < max) {
                // nums[i] needs to swap with a number on the left, so i is the right boundary.
                right = i;
            }
        }
        
        // 2nd pass from right
        int min = Integer.MAX_VALUE;
        for (int i = nums.length - 1; i >= 0; i--) {
            min = Math.min(min, nums[i]);
            if (nums[i] > min) {
                // nums[i] needs to swap with a number on the right, so i is the left boundary.
                left = i;
            }
        }
        
        return Math.max(0, right - left + 1);
    }
}

// O(N) time, O(1) space
```
