How do you solve Shortest Unsorted Continuous Subarray on LeetCode?

Shortest Unsorted Continuous Subarray (LeetCode #581) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Identifying boundaries of the unsorted subarray is crucial for efficiency.

What is the brute force solution for Shortest Unsorted Continuous Subarray?

The brute force approach for Shortest Unsorted Continuous Subarray is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves checking all possible subarrays to see if sorting them would result in the entire array being sorted. This is straightforward but inefficient for larger arrays. The optimal Optimal Solution approach improves this to O(n).

What are the interview tips for Shortest Unsorted Continuous Subarray?

Always check if the array is already sorted before proceeding. Think about how you can reduce the problem size with each step. Practice explaining your thought process clearly as you code.

What are common mistakes when solving Shortest Unsorted Continuous Subarray?

Not considering edge cases where the array is already sorted. Incorrectly expanding the boundaries of the subarray.

#581

Shortest Unsorted Continuous Subarray

Medium

ArrayTwo PointersStackGreedySortingMonotonic StackTwo PointersSliding WindowArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal approach identifies the boundaries of the unsorted subarray by finding the first and last elements that are out of order. This allows us to avoid sorting the entire array multiple times.

⚙️

Algorithm

5 steps

1Step 1: Identify the left boundary by finding the first element that is greater than the next element.
2Step 2: Identify the right boundary by finding the last element that is less than the previous element.
3Step 3: If the boundaries are found, determine the minimum and maximum values in the identified subarray.
4Step 4: Expand the boundaries if any elements outside the subarray are greater than the minimum or less than the maximum.
5Step 5: Return the length of the subarray defined by the boundaries.

solution.py19 lines

1# Full working Python code
2
3def findUnsortedSubarray(nums):
4    n = len(nums)
5    left, right = 0, n - 1
6    while left < n - 1 and nums[left] <= nums[left + 1]:
7        left += 1
8    if left == n - 1:
9        return 0
10    while right > 0 and nums[right] >= nums[right - 1]:
11        right -= 1
12    sub_min = min(nums[left:right + 1])
13    sub_max = max(nums[left:right + 1])
14    while left > 0 and nums[left - 1] > sub_min:
15        left -= 1
16    while right < n - 1 and nums[right + 1] < sub_max:
17        right += 1
18    return right - left + 1
19

ℹ

Complexity note: This complexity is achieved by making a single pass to find the boundaries and another pass to determine the min and max, resulting in linear time.

1Identifying boundaries of the unsorted subarray is crucial for efficiency.
2The min and max values in the unsorted subarray can affect the boundaries.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.