Description
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?
Solutions
Solution 1: Sorting
We can first sort the array, and then compare the sorted array with the original array to find the leftmost and rightmost positions where they differ. The length between them is the length of the shortest unsorted continuous subarray.
The time complexity is O(n × log n), and the space complexity is O(n). Here, n is the length of the array.
PythonJavaC++GoTypeScriptRust
class Solution:
def findUnsortedSubarray(self, nums: List[int]) -> int:
arr = sorted(nums)
l, r = 0, len(nums) - 1
while l <= r and nums[l] == arr[l]:
l += 1
while l <= r and nums[r] == arr[r]:
r -= 1
return r - l + 1(code-box)
class Solution {
public int findUnsortedSubarray(int[] nums) {
int[] arr = nums.clone();
Arrays.sort(arr);
int l = 0, r = arr.length - 1;
while (l <= r && nums[l] == arr[l]) {
l++;
}
while (l <= r && nums[r] == arr[r]) {
r--;
}
return r - l + 1;
}
}(code-box)
class Solution {
public:
int findUnsortedSubarray(vector<int>& nums) {
vector<int> arr = nums;
sort(arr.begin(), arr.end());
int l = 0, r = arr.size() - 1;
while (l <= r && arr[l] == nums[l]) {
l++;
}
while (l <= r && arr[r] == nums[r]) {
r--;
}
return r - l + 1;
}
};(code-box)
func findUnsortedSubarray(nums []int) int {
arr := make([]int, len(nums))
copy(arr, nums)
sort.Ints(arr)
l, r := 0, len(arr)-1
for l <= r && nums[l] == arr[l] {
l++
}
for l <= r && nums[r] == arr[r] {
r--
}
return r - l + 1
}(code-box)
function findUnsortedSubarray(nums: number[]): number {
const arr = [...nums];
arr.sort((a, b) => a - b);
let [l, r] = [0, arr.length - 1];
while (l <= r && arr[l] === nums[l]) {
++l;
}
while (l <= r && arr[r] === nums[r]) {
--r;
}
return r - l + 1;
}(code-box)
impl Solution {
pub fn find_unsorted_subarray(nums: Vec<i32>) -> i32 {
let mut arr = nums.clone();
arr.sort();
let mut l = 0usize;
while l < nums.len() && nums[l] == arr[l] {
l += 1;
}
if l == nums.len() {
return 0;
}
let mut r = nums.len() - 1;
while r > l && nums[r] == arr[r] {
r -= 1;
}
(r - l + 1) as i32
}
}(code-box)
Solution 2: Maintaining the Maximum Value on the Left and the Minimum Value on the Right
We can traverse the array from left to right and maintain a maximum value mx. If the current value is less than mx, it means that the current value is not in the correct position, and we update the right boundary r to the current position. Similarly, we can traverse the array from right to left and maintain a minimum value mi. If the current value is greater than mi, it means that the current value is not in the correct position, and we update the left boundary l to the current position. At initialization, we set l and r to -1. If l and r are not updated, it means that the array is already sorted, and we return 0. Otherwise, we return r - l + 1.
The time complexity is O(n), and the space complexity is O(1). Here, n is the length of the array.
PythonJavaC++GoTypeScriptRust
class Solution:
def findUnsortedSubarray(self, nums: List[int]) -> int:
mi, mx = inf, -inf
l = r = -1
n = len(nums)
for i, x in enumerate(nums):
if mx > x:
r = i
else:
mx = x
if mi < nums[n - i - 1]:
l = n - i - 1
else:
mi = nums[n - i - 1]
return 0 if r == -1 else r - l + 1(code-box)
class Solution {
public int findUnsortedSubarray(int[] nums) {
final int inf = 1 << 30;
int n = nums.length;
int l = -1, r = -1;
int mi = inf, mx = -inf;
for (int i = 0; i < n; ++i) {
if (mx > nums[i]) {
r = i;
} else {
mx = nums[i];
}
if (mi < nums[n - i - 1]) {
l = n - i - 1;
} else {
mi = nums[n - i - 1];
}
}
return r == -1 ? 0 : r - l + 1;
}
}(code-box)
class Solution {
public:
int findUnsortedSubarray(vector<int>& nums) {
const int inf = 1e9;
int n = nums.size();
int l = -1, r = -1;
int mi = inf, mx = -inf;
for (int i = 0; i < n; ++i) {
if (mx > nums[i]) {
r = i;
} else {
mx = nums[i];
}
if (mi < nums[n - i - 1]) {
l = n - i - 1;
} else {
mi = nums[n - i - 1];
}
}
return r == -1 ? 0 : r - l + 1;
}
};(code-box)
func findUnsortedSubarray(nums []int) int {
const inf = 1 << 30
n := len(nums)
l, r := -1, -1
mi, mx := inf, -inf
for i, x := range nums {
if mx > x {
r = i
} else {
mx = x
}
if mi < nums[n-i-1] {
l = n - i - 1
} else {
mi = nums[n-i-1]
}
}
if r == -1 {
return 0
}
return r - l + 1
}(code-box)
function findUnsortedSubarray(nums: number[]): number {
let [l, r] = [-1, -1];
let [mi, mx] = [Infinity, -Infinity];
const n = nums.length;
for (let i = 0; i < n; ++i) {
if (mx > nums[i]) {
r = i;
} else {
mx = nums[i];
}
if (mi < nums[n - i - 1]) {
l = n - i - 1;
} else {
mi = nums[n - i - 1];
}
}
return r === -1 ? 0 : r - l + 1;
}(code-box)
impl Solution {
pub fn find_unsorted_subarray(nums: Vec<i32>) -> i32 {
let inf = 1 << 30;
let n = nums.len();
let mut l = -1;
let mut r = -1;
let mut mi = inf;
let mut mx = -inf;
for i in 0..n {
if mx > nums[i] {
r = i as i32;
} else {
mx = nums[i];
}
if mi < nums[n - i - 1] {
l = (n - i - 1) as i32;
} else {
mi = nums[n - i - 1];
}
}
if r == -1 {
0
} else {
r - l + 1
}
}
}(code-box)
