LeetCode 581: Shortest Unsorted Continuous Subarray Solution

Master LeetCode problem 581 (Shortest Unsorted Continuous Subarray), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

581. Shortest Unsorted Continuous Subarray

Medium

Array Two Pointers Stack Greedy Sorting Monotonic Stack

Problem Explanation

Explanation

To solve this problem in O(n) time complexity, we can use a two-pointer approach. We will use two pointers, left and right, to find the subarray that needs to be sorted. We will iterate from left to right to find the right boundary of the subarray and then iterate from right to left to find the left boundary of the subarray.

Here is the step-by-step algorithm:

Initialize left and right pointers to 0 and n-1 respectively.
Move the right pointer towards the left as long as the elements are in non-decreasing order.
Move the left pointer towards the right as long as the elements are in non-decreasing order.
Find the minimum and maximum elements in the subarray between left and right.
Move the right pointer towards the left until it reaches the last element less than the maximum element found in step 4.
Move the left pointer towards the right until it reaches the first element greater than the minimum element found in step 4.
The subarray between left and right is the shortest unsorted continuous subarray.

The time complexity of this approach is O(n) where n is the length of the input array. The space complexity is O(1) as we are using constant extra space.

Solution Code

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        int left = 0, right = n - 1;

        while (left < n - 1 && nums[left] <= nums[left + 1]) {
            left++;
        }

        if (left == n - 1) {
            return 0;
        }

        while (right > 0 && nums[right] >= nums[right - 1]) {
            right--;
        }

        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for (int i = left; i <= right; i++) {
            min = Math.min(min, nums[i]);
            max = Math.max(max, nums[i]);
        }

        while (left > 0 && nums[left - 1] > min) {
            left--;
        }

        while (right < n - 1 && nums[right + 1] < max) {
            right++;
        }

        return right - left + 1;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 581 (Shortest Unsorted Continuous Subarray)?

This page provides optimized solutions for LeetCode problem 581 (Shortest Unsorted Continuous Subarray) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 581 (Shortest Unsorted Continuous Subarray)?

The time complexity for LeetCode 581 (Shortest Unsorted Continuous Subarray) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 581 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 581 in Java, C++, or Python.

Back to LeetCode Solutions