581. Shortest Unsorted Continuous Subarray
Last updated
Last updated
/**
* Time complexity : O(n^2). Two nested loops are there.
* Space complexity : O(1). Constant space is used.
*/
public class Solution {
public int findUnsortedSubarray(int[] nums) {
int l = nums.length, r = 0;
for (int i = 0; i < nums.length - 1; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] < nums[i]) {
r = Math.max(r, j);
l = Math.min(l, i);
}
}
}
return r - l < 0 ? 0 : r - l + 1;
}
}/**
* Time complexity : O(nlogn). Sorting takes nlogn time.
* Space complexity : O(n). We are making copy of original array.
*/
public class Solution {
public int findUnsortedSubarray(int[] nums) {
int[] snums = nums.clone();
Arrays.sort(snums);
int start = snums.length, end = 0;
for (int i = 0; i < snums.length; i++) {
if (snums[i] != nums[i]) {
start = Math.min(start, i);
end = Math.max(end, i);
}
}
return (end - start >= 0 ? end - start + 1 : 0);
}
}/**
* Time complexity : O(n). Stack of size n is filled.
* Space complexity : O(n). Stack size grows upto n.
*/
public class Solution {
public int findUnsortedSubarray(int[] nums) {
Stack < Integer > stack = new Stack < Integer > ();
int l = nums.length, r = 0;
for (int i = 0; i < nums.length; i++) {
while (!stack.isEmpty() && nums[stack.peek()] > nums[i])
l = Math.min(l, stack.pop());
stack.push(i);
}
stack.clear();
for (int i = nums.length - 1; i >= 0; i--) {
while (!stack.isEmpty() && nums[stack.peek()] < nums[i])
r = Math.max(r, stack.pop());
stack.push(i);
}
return r - l > 0 ? r - l + 1 : 0;
}
}/**
* Time complexity : O(n). Two O(n) loops are used.
* Space complexity : O(1). Constant space is used.
*/
class Solution {
public int findUnsortedSubarray(int[] nums) {
if(nums == null || nums.length <= 1) {
return 0;
}
int n = nums.length;
int end = 0;
int max = nums[0];
for(int i = 0; i < n; i++) {
if(nums[i] >= max) {
max = nums[i];
} else {
end = i;
}
}
int start = n;
int min = nums[n-1];
for(int i = n-1; i >= 0; i--) {
if(nums[i] <= min) {
min = nums[i];
} else {
start = i;
}
}
return (start == n)? 0:end-start+1;
}
}