#581

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Shortest Unsorted Continuous Subarray

Find the shortest unsorted continuous subarray that, if sorted, would sort the entire array.

Problem Statement

Given an integer array nums, you need to find the shortest continuous subarray such that if you sort only that subarray in non-decreasing order, the entire array will become sorted in non-decreasing order.

Return the length of the shortest subarray that needs to be sorted. If the entire array is already sorted, return 0.

Examples

Example 1

Input: nums = [2,6,4,8,10,9,15]

Output: 5

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 details omitted.

Example 3

Input: nums = [1]

Output: 0

Example details omitted.

Constraints

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

Solution Approach

Two-pointer Scanning

Start with two pointers, one from the left and one from the right, and scan the array to find where the unsorted portion starts and ends. This helps identify the boundaries of the subarray that requires sorting.

Invariant Tracking

As you scan the array, track the invariant that should hold for a sorted array. The subarray to be sorted can be found where this invariant breaks, and by adjusting the pointers accordingly, you can define the bounds of the required subarray.

Return Subarray Length

Once the boundaries of the subarray are identified, calculate the length of this subarray and return the result. This length represents the smallest subarray that needs to be sorted to achieve a fully sorted array.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the final implementation but is typically O(n) where n is the length of the array. Space complexity can vary, but an optimal solution uses O(1) space with two-pointer scanning.

What Interviewers Usually Probe

The candidate should efficiently identify the boundaries of the unsorted subarray using a two-pointer technique.
The interviewee should demonstrate how they maintain the invariant during the scanning process.
Look for a clear and optimal solution where the candidate explains the reasoning behind their approach.

Common Pitfalls or Variants

Common pitfalls

Not updating the pointers correctly when scanning for the unsorted boundaries.
Overlooking edge cases, like an already sorted array or a very short array.
Confusing the invariant, leading to unnecessary subarray checks or inefficiencies.

Follow-up variants

Modify the problem to handle arrays that may contain duplicate elements.
Extend the problem by asking to sort the identified subarray and return the fully sorted array.
Introduce constraints on time complexity, such as requiring a solution that operates in O(n log n) or better.

FAQ

How do I approach the Shortest Unsorted Continuous Subarray problem?

You can solve it efficiently using two-pointer scanning and invariant tracking to identify the smallest subarray that needs sorting.

What is the time complexity of the optimal solution?

The optimal solution typically has a time complexity of O(n), where n is the length of the array.

What if the array is already sorted?

In that case, the length of the subarray to be sorted is 0, as no sorting is needed.

How do I handle edge cases in this problem?

Edge cases, like arrays with one element or already sorted arrays, should be handled by checking for the absence of unsorted segments.

What is invariant tracking, and how does it help solve the problem?

Invariant tracking involves ensuring that the array maintains a sorted order. By tracking where this invariant breaks, you can pinpoint the boundaries of the subarray to sort.

terminal

Solution

Solution 1: Sorting

We can first sort the array, and then compare the sorted array with the original array to find the leftmost and rightmost positions where they differ. The length between them is the length of the shortest unsorted continuous subarray.

1

2

3

4

5

6

7

8

9

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        arr = sorted(nums)
        l, r = 0, len(nums) - 1
        while l <= r and nums[l] == arr[l]:
            l += 1
        while l <= r and nums[r] == arr[r]:
            r -= 1
        return r - l + 1

Solution 2: Maintaining the Maximum Value on the Left and the Minimum Value on the Right

We can traverse the array from left to right and maintain a maximum value $mx$. If the current value is less than $mx$, it means that the current value is not in the correct position, and we update the right boundary $r$ to the current position. Similarly, we can traverse the array from right to left and maintain a minimum value $mi$. If the current value is greater than $mi$, it means that the current value is not in the correct position, and we update the left boundary $l$ to the current position. At initialization, we set $l$ and $r$ to $-1$. If $l$ and $r$ are not updated, it means that the array is already sorted, and we return $0$. Otherwise, we return $r - l + 1$.

1

2

3

4

5

6

7

8

9

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        arr = sorted(nums)
        l, r = 0, len(nums) - 1
        while l <= r and nums[l] == arr[l]:
            l += 1
        while l <= r and nums[r] == arr[r]:
            r -= 1
        return r - l + 1

Continue Practicing

#768 max chunks to make sorted ii #769 max chunks to make sorted #321 create maximum number