Solution to LC-581 (Shortest Unsorted Continuous Subarray)

shortest-unsorted-continuous-subarray.ts

const findUnsortedSubarray = (nums: number[]): number => {
    // find the left order breaker
    let left = 0;
    while (left < nums.length - 1 && nums[left] <= nums[left + 1]) {
        left++;
    }

    // if left is the last element, then the array is already sorted
    if (left === nums.length - 1) {
        return 0;
    }

    // find the right order breaker
    let right = nums.length - 1;
    while (right > 0 && nums[right] >= nums[right - 1]) {
        right--;
    }

    // find the min and max between left and right
    let min = Number.MAX_SAFE_INTEGER;
    let max = Number.MIN_SAFE_INTEGER;

    for (let i = left; i <= right; i++) {
        min = Math.min(min, nums[i]);
        max = Math.max(max, nums[i]);
    }

    // find the correct position of min and max
    while (left >= 0 && nums[left] > min) {
        left--;
    }

    // find the correct position of max
    while (right < nums.length && nums[right] < max) {
        right++;
    }

    return right - left - 1;
}

const testFindUnsortedSubarray = () => {
    // Generate 10000 random arrays

    for (let i = 0; i < 10000; i++) {
        // Generate random length
        const length = Math.floor(Math.random() * 100) + 1;
        // Generate a random sorted array by generating a random array of small numbers and making them into plus operations
        const increaseArray = Array.from({ length }, () => Math.floor(Math.random() * 3));
        const nums = increaseArray.reduce((acc, cur) => {
            acc.push(acc[acc.length - 1] + cur);
            return acc;
        }, [0]);
        // Pick two random indexes and swap them
        const index1 = Math.floor(Math.random() * length);
        const index2 = Math.floor(Math.random() * length);

        if (nums[index1] === nums[index2]) {
            continue;
        }
        const temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;

        const result = findUnsortedSubarray(nums);

        // Result should be the difference between the two indexes
        if (result !== Math.abs(index1 - index2) + 1) {
            console.log('Test failed');
            console.log(nums);
            console.log("result:", result);
            console.log("indexes:", index1, index2);
            console.log("expected:", Math.abs(index1 - index2 + 1));
            return;
        }
    }
}

// console.log(findUnsortedSubarray([2, 6, 4, 8, 10, 9, 15])); // Expected 5

// console.log(findUnsortedSubarray([1, 2, 3, 4])); // Expected 0

// console.log(findUnsortedSubarray([1, 2, 3, 3, 3])); // Expected 0

// console.log(findUnsortedSubarray([1, 2, 3, 5, 4])); // Expected 2

// console.log(findUnsortedSubarray([1, 3, 2, 2, 2])); // Expected 4
// console.log(findUnsortedSubarray([2, 2, 2, 1, 3])); // Expected 4

// console.log(findUnsortedSubarray([1,2,4,5,3])); // Expected 3

testFindUnsortedSubarray();