Is Shortest Unsorted Continuous Subarray easy or hard?

Shortest Unsorted Continuous Subarray is classified as a Medium problem on LeetCode. The difficulty comes from recognizing that you can detect disorder using running minimum and maximum values instead of sorting the entire array.

How to solve Shortest Unsorted Continuous Subarray in O(n)?

Scan from the left while maintaining the maximum value seen so far. Whenever the current element is smaller than this maximum, update the right boundary. Then scan from the right while maintaining the minimum value; when the current element exceeds it, update the left boundary. The segment between these boundaries is the answer.

What is the best approach for Shortest Unsorted Continuous Subarray?

The best approach is the linear scan using minimum and maximum deviations. Traverse left to right while tracking the maximum value to detect the right boundary, then traverse right to left tracking the minimum value to find the left boundary. This method runs in O(n) time and uses O(1) extra space.

What data structure is used in Shortest Unsorted Continuous Subarray?

Most solutions rely only on basic array traversal with running minimum and maximum values. Some implementations also use a monotonic stack to detect ordering violations, which helps identify the left and right boundaries of the unsorted segment.

What is the time complexity of Shortest Unsorted Continuous Subarray?

The optimal solution runs in O(n) time with O(1) extra space using two directional scans. A simpler alternative sorts a copy of the array and compares positions, which takes O(n log n) time and O(n) space.

Shortest Unsorted Continuous Subarray Python or Java solution approach?

Both Python and Java implementations typically use the O(n) greedy scan. Track a running maximum during a forward pass and a running minimum during a backward pass to identify boundaries. The algorithm uses constant extra space and works efficiently for large arrays.

Is Shortest Unsorted Continuous Subarray asked at Google, Amazon, or Meta?

This problem represents a common interview pattern involving array order violations and greedy boundary detection. Variants of this question appear in interviews at large tech companies such as Amazon, Google, and Meta because it tests array reasoning and linear-time optimization.

581. Shortest Unsorted Continuous Subarray - Practice Online

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 <= 10⁴
-10⁵ <= nums[i] <= 10⁵

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