581. Shortest Unsorted Continuous Subarray

Problem

Given an integer array nums, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending 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

Problem Summary

Given an integer array nums, you need to find one continuous subarray such that if you sort this subarray in ascending order, then the whole array will become sorted in ascending order. Please find the shortest subarray that satisfies the requirement and output its length.

Solution Approach

• This problem asks for the shortest inversion interval. After simple reasoning, we can know that this inversion interval must have its left boundary determined by the minimum element within the interval and its right boundary determined by the maximum element.
• First, find the first descending element from the left and record the minimum element min, then find the rightmost element that starts descending from the right to the left and record the maximum element max. Finally, we need to restore the correct positions of the minimum element and maximum element in the original array. Take the left boundary of the inversion interval as an example: if an element outside the interval is smaller than the minimum element inside this inversion interval, it means it is not the left boundary, because this small element together with the minimum element inside the inversion interval is still in ascending order, not inverted. Only when the first element greater than the minimum element inside the inversion interval is found outside the left interval does it indicate that an inversion has just started here, and this is the left boundary of the minimum inversion interval. Similarly, finding the first element smaller than the maximum element inside the inversion interval on the right side of the inversion interval indicates that an inversion has just occurred here, and this is the right boundary of the minimum inversion interval. At this point, both the left and right boundaries of the minimum inversion interval have been determined, and the shortest length is also determined. Time complexity is O(n), and space complexity is O(1).

Code

package leetcode

import "math"

func findUnsortedSubarray(nums []int) int {
	n, left, right, minR, maxL, isSort := len(nums), -1, -1, math.MaxInt32, math.MinInt32, false
	// left
	for i := 1; i < n; i++ {
		if nums[i] < nums[i-1] {
			isSort = true
		}
		if isSort {
			minR = min(minR, nums[i])
		}
	}
	isSort = false
	// right
	for i := n - 2; i >= 0; i-- {
		if nums[i] > nums[i+1] {
			isSort = true
		}
		if isSort {
			maxL = max(maxL, nums[i])
		}
	}
	// minR
	for i := 0; i < n; i++ {
		if nums[i] > minR {
			left = i
			break
		}
	}
	// maxL
	for i := n - 1; i >= 0; i-- {
		if nums[i] < maxL {
			right = i
			break
		}
	}
	if left == -1 || right == -1 {
		return 0
	}
	return right - left + 1
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}