581. Shortest Unsorted Continuous Subarray LeetCode Solution

In this guide, you will get 581. Shortest Unsorted Continuous Subarray LeetCode Solution with the best time and space complexity. The solution to Shortest Unsorted Continuous Subarray problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Shortest Unsorted Continuous Subarray solution in C++
4. Shortest Unsorted Continuous Subarray solution in Java
5. Shortest Unsorted Continuous Subarray solution in Python
6. Additional Resources

Problem Statement of Shortest Unsorted Continuous Subarray

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 <= 104
-105 <= nums[i] <= 105

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

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

581. Shortest Unsorted Continuous Subarray LeetCode Solution in C++

class Solution {
 public:
  int findUnsortedSubarray(vector<int>& nums) {
    const int n = nums.size();
    int mn = INT_MAX;
    int mx = INT_MIN;
    bool meetDecrease = false;
    bool meetIncrease = false;

    for (int i = 1; i < n; ++i) {
      if (nums[i] < nums[i - 1])
        meetDecrease = true;
      if (meetDecrease)
        mn = min(mn, nums[i]);
    }

    for (int i = n - 2; i >= 0; --i) {
      if (nums[i] > nums[i + 1])
        meetIncrease = true;
      if (meetIncrease)
        mx = max(mx, nums[i]);
    }

    int l;
    for (l = 0; l < n; ++l)
      if (nums[l] > mn)
        break;

    int r;
    for (r = n - 1; r >= 0; --r)
      if (nums[r] < mx)
        break;

    return l < r ? r - l + 1 : 0;
  }
};
/* code provided by PROGIEZ */

581. Shortest Unsorted Continuous Subarray LeetCode Solution in Java

class Solution {
  public int findUnsortedSubarray(int[] nums) {
    final int n = nums.length;
    int mn = Integer.MAX_VALUE;
    int mx = Integer.MIN_VALUE;
    boolean meetDecrease = false;
    boolean meetIncrease = false;

    for (int i = 1; i < n; ++i) {
      if (nums[i] < nums[i - 1])
        meetDecrease = true;
      if (meetDecrease)
        mn = Math.min(mn, nums[i]);
    }

    for (int i = n - 2; i >= 0; --i) {
      if (nums[i] > nums[i + 1])
        meetIncrease = true;
      if (meetIncrease)
        mx = Math.max(mx, nums[i]);
    }

    int l = 0;
    for (l = 0; l < n; ++l)
      if (nums[l] > mn)
        break;

    int r = 0;
    for (r = n - 1; r >= 0; --r)
      if (nums[r] < mx)
        break;

    return l > r ? 0 : r - l + 1;
  }
}
// code provided by PROGIEZ

581. Shortest Unsorted Continuous Subarray LeetCode Solution in Python

class Solution:
  def findUnsortedSubarray(self, nums: list[int]) -> int:
    mn = math.inf
    mx = -math.inf
    flag = False

    for i in range(1, len(nums)):
      if nums[i] < nums[i - 1]:
        flag = True
      if flag:
        mn = min(mn, nums[i])

    flag = False

    for i in reversed(range(len(nums) - 1)):
      if nums[i] > nums[i + 1]:
        flag = True
      if flag:
        mx = max(mx, nums[i])

    for l in range(len(nums)):
      if nums[l] > mn:
        break

    for r, num in reversed(list(enumerate(nums))):
      if num < mx:
        break

    return 0 if l >= r else r - l + 1
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.