-
Notifications
You must be signed in to change notification settings - Fork 1
/
LeetCode_581_Easy_BF.js
70 lines (59 loc) · 2.27 KB
/
LeetCode_581_Easy_BF.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/**
* @param {number[]} nums
* @return {number}
*/
// Input: An integer array with 0 or more elements.
// Outout: Minimum Continuous subarray length
// Condition: If subarray is sorted, then the entire array would be sorted.
// O(n * n) run-time, O(1) space time
var findUnsortedSubarray = function(nums) {
// Brute force solution:
// Find all the possible pairs of indexes that can make a subarry.
// Since we are looking for the shortest subarray as the result, we should expand the brute force array such that we increase the length of it.
// For each shortest subarray, sort the subarray and check if the entire array is now sorted.
// In the brute force solution, we are exploiting few properties of the solution state:
// 1. Left subarray would be sorted.
// 2. Right subarray would be sorted.
// 3. Min of center subarray is >= last element of left.
// 4. Max of center subarray is <= 1st element of right.
if (nums.length <= 1 || isSorted(nums)) {
return 0
}
for (let windowSize=2;windowSize<=nums.length;windowSize++) {
for (let leftIdx=0;leftIdx<=nums.length - windowSize;leftIdx++) {
const rightIdx = leftIdx + windowSize
const [min, max] = findMinMax(nums, leftIdx, rightIdx)
// console.log(leftIdx, rightIdx, min, max)
if (isSorted(nums, 0, leftIdx) &&
isSorted(nums, rightIdx, nums.length) &&
(leftIdx === 0 ? true : nums[leftIdx-1] <= min) &&
(rightIdx === nums.length ? true : nums[rightIdx] >= max)) {
return windowSize
}
}
}
return nums.length
};
// Finding the min and the max number from a given array.
function findMinMax(nums, start, end) {
let min = nums[start]
let max = nums[start]
for (let i=start+1;i<end;i++) {
if (nums[i] < min) {
min = nums[i]
}
if (nums[i] > max) {
max = nums[i]
}
}
return [min, max]
}
// Find if the array is sorted
function isSorted(nums, start = 0, end = nums.length) {
let last = nums[start]
for (let i=start+1;i<end;i++) {
if (nums[i] < last) return false
last = nums[i]
}
return true
}