# Shortest Unsorted Continuous Subarray
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/shortest-unsorted-continuous-subarray)
Canonical: https://scaleengineer.com/dsa/problems/shortest-unsorted-continuous-subarray
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Stack, Monotonic Stack
**Companies:** [LiveRamp](https://scaleengineer.com/companies/liveramp)
---
## Problem
Given an integer array `nums`, you need to find one **continuous subarray** such that if you only sort this subarray in non-decreasing order, then the whole array will be sorted in non-decreasing 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?

# Approaches
## Comparison with Sorted Array
This approach involves creating a sorted version of the input array and comparing it with the original array. The boundaries of the required subarray are determined by the first and last positions where the elements of the original array and the sorted array do not match.
**Time:** O(n log n) - The dominant operation is sorting the array, which typically takes `O(n log n)` time. The subsequent linear scans take `O(n)` time. · **Space:** O(n) - A copy of the input array is created for sorting, which requires space proportional to the number of elements, `n`.
**Pros:** Simple to conceptualize and implement.; Correctly handles all edge cases, including already sorted arrays.
**Cons:** The time complexity is dominated by the sorting algorithm, making it slower than linear-time solutions.; Requires extra space proportional to the input array size to hold the sorted copy.
### Explanation
The most straightforward way to identify the unsorted portion of an array is to have a sorted version of it for reference. By comparing the original array `nums` with its sorted counterpart, we can pinpoint exactly which elements are out of place.

We start by creating a copy of `nums` and sorting it. Then, we iterate from both ends of the arrays inward. The first index from the left where `nums[i]` and `sorted_nums[i]` are different gives us the left boundary of the unsorted subarray. Similarly, the first mismatch from the right gives us the right boundary. If no mismatches are found, the array is already sorted, and the length is 0. Otherwise, the result is the distance between these two boundaries, inclusive.

```java
import java.util.Arrays;

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int[] sorted_nums = nums.clone();
        Arrays.sort(sorted_nums);
        
        int start = nums.length, end = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != sorted_nums[i]) {
                start = Math.min(start, i);
                end = Math.max(end, i);
            }
        }
        
        if (end - start >= 0) {
            return end - start + 1;
        } else {
            return 0;
        }
    }
}
```
### Algorithm
- Create a clone of the input array `nums` and name it `sorted_nums`.
- Sort the `sorted_nums` array in non-decreasing order.
- If `nums` is identical to `sorted_nums`, the array is already sorted, so return 0.
- Find the first index from the left, `left`, where `nums[left]` differs from `sorted_nums[left]`.
- Find the first index from the right, `right`, where `nums[right]` differs from `sorted_nums[right]`.
- The length of the shortest unsorted subarray is `right - left + 1`.

## Stack-Based Approach
A more efficient approach uses a stack to determine the boundaries of the unsorted subarray in a single pass for each boundary. By maintaining a monotonic stack (increasing for the left boundary, decreasing for the right boundary), we can identify the indices of elements that violate the sorted order and find the outermost such indices.
**Time:** O(n) - The algorithm consists of two separate passes through the array. In each pass, every element is pushed onto and popped from the stack at most once. · **Space:** O(n) - In the worst-case scenario (e.g., a fully sorted array), the stack can grow to hold all `n` indices.
**Pros:** Achieves optimal O(n) time complexity.; Provides an elegant way to find boundaries by identifying out-of-order elements.
**Cons:** Requires O(n) extra space for the stack, which is less optimal than a constant space solution.
### Explanation
This method cleverly uses a stack to find the correct boundaries `left` and `right` in linear time. 

To find the left boundary, we iterate from the beginning of the array. We maintain a stack of indices whose corresponding elements are in increasing order. When we encounter an element `nums[i]` that is smaller than the element at the stack's top, it signifies a disorder. The element at the stack's top is too large for its position and must be part of the unsorted subarray. We pop from the stack and update our candidate for the left boundary (`left`) with the popped index. We continue this until the stack top is smaller than `nums[i]` or the stack is empty. This ensures `left` is the smallest index of an element that is larger than some element to its right.

To find the right boundary, we perform a symmetric operation, iterating from the end of the array. We maintain a stack of indices for elements in decreasing order. When we find an element `nums[i]` larger than the stack's top, we know the top element is too small for its position. We pop and update the right boundary (`right`).

```java
import java.util.Stack;

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        Stack<Integer> stack = new Stack<>();
        int left = nums.length, right = -1;

        // Find the left boundary
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
                left = Math.min(left, stack.pop());
            }
            stack.push(i);
        }

        stack.clear();

        // Find the right boundary
        for (int i = nums.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                right = Math.max(right, stack.pop());
            }
            stack.push(i);
        }

        return right > left ? right - left + 1 : 0;
    }
}
```
### Algorithm
- Initialize `left = n` (where `n` is the array length) and `right = -1`.
- **First Pass (to find `left`):**
  - Use a stack to keep track of indices in increasing order of their corresponding values.
  - Iterate through the array from left to right. For each element `nums[i]`, if it's smaller than the value at the index on top of the stack, it means the top element is out of place. Pop from the stack and update `left = min(left, popped_index)`.
  - Push the current index `i` onto the stack.
- **Second Pass (to find `right`):**
  - Clear the stack.
  - Use the stack to keep track of indices in decreasing order of their corresponding values.
  - Iterate through the array from right to left. For each element `nums[i]`, if it's larger than the value at the index on top of the stack, pop and update `right = max(right, popped_index)`.
  - Push the current index `i` onto the stack.
- If `right > left`, the length is `right - left + 1`. Otherwise, the array is sorted, and the length is 0.

## Constant Space Linear Time Approach
This optimal approach solves the problem in linear time and constant space. It works by first identifying the minimum and maximum values that are out of their sorted positions. Then, it determines the correct placement for these values, which in turn defines the boundaries of the shortest unsorted continuous subarray.
**Time:** O(n) - The algorithm involves a constant number of passes (four in this implementation) over the array, resulting in a linear time complexity. · **Space:** O(1) - The algorithm uses a fixed number of variables to store the minimum and maximum values and the boundaries, regardless of the input size.
**Pros:** Most efficient solution with O(n) time and O(1) space complexity.; Avoids the overhead of data structures like stacks or creating array copies.
**Cons:** The logic can be less intuitive to come up with compared to the sorting approach.; It requires multiple passes over the array, though the overall complexity remains linear.
### Explanation
The key insight is that the subarray we need to sort is bounded by the correct positions of the smallest and largest out-of-place numbers. 

The algorithm proceeds in two main stages:

1.  **Find the range of values in the unsorted subarray:** We can find the minimum element (`min_val`) that is out of place by finding any element that is smaller than its preceding element. Similarly, the maximum element (`max_val`) that is out of place can be found by identifying any element larger than its succeeding element. We iterate through the array to find the absolute minimum and maximum of all such out-of-place elements.

2.  **Find the boundaries of the subarray:** Once we have `min_val` and `max_val`, the entire subarray from `nums[0]` up to the correct position of `max_val` might need reordering. Likewise, the subarray from the correct position of `min_val` to the end might need reordering. Therefore, the left boundary of our final subarray is the first index from the left that is greater than `min_val`. The right boundary is the first index from the right that is less than `max_val`.

This method requires a few passes over the array but uses only a constant amount of extra space for variables.

```java
class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int min_val = Integer.MAX_VALUE;
        int max_val = Integer.MIN_VALUE;
        boolean flag = false;

        // Find the minimum element of the unsorted subarray
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < nums[i - 1]) {
                flag = true;
            }
            if (flag) {
                min_val = Math.min(min_val, nums[i]);
            }
        }

        flag = false;
        // Find the maximum element of the unsorted subarray
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] > nums[i + 1]) {
                flag = true;
            }
            if (flag) {
                max_val = Math.max(max_val, nums[i]);
            }
        }

        if (min_val == Integer.MAX_VALUE) { // Array is sorted
            return 0;
        }

        int left, right;
        // Find the correct position for min_val (left boundary)
        for (left = 0; left < nums.length; left++) {
            if (nums[left] > min_val) {
                break;
            }
        }

        // Find the correct position for max_val (right boundary)
        for (right = nums.length - 1; right >= 0; right--) {
            if (nums[right] < max_val) {
                break;
            }
        }

        return right - left + 1;
    }
}
```
### Algorithm
- Initialize `min_val = Integer.MAX_VALUE` and `max_val = Integer.MIN_VALUE`.
- **Step 1: Find the minimum and maximum of the disordered subarray.**
  - Iterate from `i = 1` to `n-1`. If `nums[i] < nums[i-1]`, we've found a dip. This `nums[i]` is part of the unsorted section. Update `min_val = min(min_val, nums[i])`.
  - Iterate from `i = n-2` down to `0`. If `nums[i] > nums[i+1]`, we've found a peak. This `nums[i]` is part of the unsorted section. Update `max_val = max(max_val, nums[i])`.
- If `min_val` remains `Integer.MAX_VALUE`, the array is already sorted; return 0.
- **Step 2: Find the correct boundaries for `min_val` and `max_val`.**
  - Find the left boundary `left` by iterating from the start of the array. `left` is the first index `l` where `nums[l] > min_val`.
  - Find the right boundary `right` by iterating from the end of the array. `right` is the first index `r` where `nums[r] < max_val`.
- The result is `right - left + 1`.

# Solutions
### Java

```java
class Solution {
public
  int findUnsortedSubarray(int[] nums) {
    final int inf = 1 << 30;
    int n = nums.length;
    int l = -1, r = -1;
    int mi = inf, mx = -inf;
    for (int i = 0; i < n; ++i) {
      if (mx > nums[i]) {
        r = i;
      } else {
        mx = nums[i];
      }
      if (mi < nums[n - i - 1]) {
        l = n - i - 1;
      } else {
        mi = nums[n - i - 1];
      }
    }
    return r == -1 ? 0 : r - l + 1;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int findUnsortedSubarray(vector<int> &nums) {
    const int inf = 1e9;
    int n = nums.size();
    int l = -1, r = -1;
    int mi = inf, mx = -inf;
    for (int i = 0; i < n; ++i) {
      if (mx > nums[i]) {
        r = i;
      } else {
        mx = nums[i];
      }
      if (mi < nums[n - i - 1]) {
        l = n - i - 1;
      } else {
        mi = nums[n - i - 1];
      }
    }
    return r == -1 ? 0 : r - l + 1;
  }
};

```

### Python

```python
class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int: mi, mx = inf, - inf l = r = - 1 n = len(nums) for i, x in enumerate(nums): if mx > x: r = i else: mx = x if mi < nums[n - i - 1]: l = n - i - 1 else: mi = nums[n - i - 1] return 0 if r == - 1 else r - l + 1

```