# LeetCode 581: Shortest Unsorted Continuous Subarray

## Problem Restatement

We are given an integer array `nums`.

We need to find the shortest continuous subarray such that, if we sort only that subarray in non-decreasing order, the whole array becomes sorted in non-decreasing order.

Return the length of that subarray.

If the array is already sorted, return `0`. The constraints are `1 <= nums.length <= 10^4` and `-10^5 <= nums[i] <= 10^5`. The follow-up asks for an `O(n)` solution.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer array `nums` |
| Output | Length of the shortest continuous subarray to sort |
| Already sorted | Return `0` |

Example function shape:

```python
def findUnsortedSubarray(nums: list[int]) -> int:
    ...
```

## Examples

Example 1:

```python
nums = [2, 6, 4, 8, 10, 9, 15]
```

Output:

```python
5
```

The subarray is:

```python
[6, 4, 8, 10, 9]
```

If we sort only this part, the array becomes:

```python
[2, 4, 6, 8, 9, 10, 15]
```

So the answer is `5`.

Example 2:

```python
nums = [1, 2, 3, 4]
```

Output:

```python
0
```

The array is already sorted.

Example 3:

```python
nums = [1]
```

Output:

```python
0
```

A single-element array is already sorted.

## First Thought: Sort and Compare

A simple solution is to compare the array with its sorted version.

```python
nums        = [2, 6, 4, 8, 10, 9, 15]
sorted_nums = [2, 4, 6, 8, 9, 10, 15]
```

The first index where they differ is `1`.

The last index where they differ is `5`.

So the shortest subarray length is:

```python
5 - 1 + 1 = 5
```

This approach is easy and correct, but it costs `O(n log n)` time because of sorting.

The follow-up asks for `O(n)`, so we can do better.

## Key Insight

We need to find the left and right boundaries of the unsorted region.

The right boundary is the last index where the current value is smaller than something before it.

Scan from left to right while tracking the maximum value seen so far.

If:

```python
nums[i] < max_seen
```

then `nums[i]` is too small to stay at index `i`. It must be inside the unsorted subarray. So we update the right boundary.

The left boundary is symmetric.

Scan from right to left while tracking the minimum value seen so far.

If:

```python
nums[i] > min_seen
```

then `nums[i]` is too large to stay at index `i`. It must be inside the unsorted subarray. So we update the left boundary.

## Algorithm

1. Set `right = -1`.
2. Scan from left to right.
3. Track `max_seen`, the largest value seen so far.
4. If `nums[i] < max_seen`, update `right = i`.

Then:

1. Set `left = 0`.
2. Scan from right to left.
3. Track `min_seen`, the smallest value seen so far.
4. If `nums[i] > min_seen`, update `left = i`.

Finally:

1. If `right == -1`, the array is already sorted.
2. Otherwise, return `right - left + 1`.

## Correctness

During the left-to-right scan, `max_seen` is the largest value among all elements from index `0` to index `i`.

If `nums[i] < max_seen`, then some earlier value is greater than `nums[i]`. Therefore, the array cannot be sorted unless index `i` is included in the subarray to be sorted. Updating `right = i` ensures that the right boundary reaches every such out-of-order position.

If `nums[i] >= max_seen`, then `nums[i]` is at least as large as every value before it, so this scan gives no reason to include index `i` as a right-side violation.

During the right-to-left scan, `min_seen` is the smallest value among all elements from index `i` to the end.

If `nums[i] > min_seen`, then some later value is smaller than `nums[i]`. Therefore, the array cannot be sorted unless index `i` is included in the subarray to be sorted. Updating `left = i` ensures that the left boundary reaches every such out-of-order position.

After both scans, every index outside `[left, right]` is already compatible with the sorted order of all elements around it. Every index that must move because of a larger earlier value or smaller later value is included. Therefore, sorting exactly `nums[left:right + 1]` is sufficient and minimal.

If no right-side violation is found, then no element is smaller than a previous maximum. That means the entire array is already non-decreasing, so the correct answer is `0`.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan the array twice |
| Space | `O(1)` | We use only a few variables |

## Implementation

```python
class Solution:
    def findUnsortedSubarray(self, nums: list[int]) -> int:
        n = len(nums)

        max_seen = nums[0]
        right = -1

        for i in range(n):
            if nums[i] < max_seen:
                right = i
            else:
                max_seen = nums[i]

        min_seen = nums[-1]
        left = 0

        for i in range(n - 1, -1, -1):
            if nums[i] > min_seen:
                left = i
            else:
                min_seen = nums[i]

        if right == -1:
            return 0

        return right - left + 1
```

## Code Explanation

This variable stores the largest value seen while scanning from left to right:

```python
max_seen = nums[0]
```

The right boundary starts at `-1`:

```python
right = -1
```

If the array is already sorted, `right` will never change.

During the left-to-right scan:

```python
if nums[i] < max_seen:
    right = i
else:
    max_seen = nums[i]
```

If the current number is smaller than a previous number, it is out of order. So it must be inside the subarray.

Then we scan from right to left:

```python
min_seen = nums[-1]
left = 0
```

During this scan:

```python
if nums[i] > min_seen:
    left = i
else:
    min_seen = nums[i]
```

If the current number is larger than a later number, it is out of order. So it must be inside the subarray.

Finally:

```python
if right == -1:
    return 0
```

No violation means the array is already sorted.

Otherwise:

```python
return right - left + 1
```

This returns the length of the shortest subarray.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.findUnsortedSubarray([2, 6, 4, 8, 10, 9, 15]) == 5
    assert s.findUnsortedSubarray([1, 2, 3, 4]) == 0
    assert s.findUnsortedSubarray([1]) == 0
    assert s.findUnsortedSubarray([1, 3, 2, 2, 2]) == 4
    assert s.findUnsortedSubarray([2, 1]) == 2
    assert s.findUnsortedSubarray([1, 2, 4, 5, 3]) == 3

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[2, 6, 4, 8, 10, 9, 15]` | Main sample |
| `[1, 2, 3, 4]` | Already sorted |
| `[1]` | Minimum length |
| `[1, 3, 2, 2, 2]` | Handles duplicates |
| `[2, 1]` | Entire array must be sorted |
| `[1, 2, 4, 5, 3]` | Left boundary expands past the local inversion |