Shortest Unsorted Continuous Subarray

1. Problem Description

Given an integer array nums, find a continuous subarray such that sorting only this subarray in ascending order makes the whole array sorted in ascending order.

Return the length of the shortest such subarray.

2. Approach

1. Approach 1
   • Sort a copy of all elements
   • Compare it with the original array
   • From left to right, find the first different element; from right to left, find the first different element
   • Their distance gives the answer

3. Implementation

3.1. Sorting

func findUnsortedSubarray(nums []int) int {
    dst := make([]int, len(nums))
    copy(dst, nums)
    mergeSort(dst,0,len(dst)-1)
    

    left := 0
    for i := 0; i < len(nums); i++ {
        if dst[i] != nums[i] {
            left = i
            break
        }
    }

    right := 0
    for i := len(nums)-1; i >= 0; i-- {
        if dst[i] != nums[i] {
            right = i
            break
        }
    }  

    if left == 0 && right == 0 {
        return 0
    }

    return right-left+1
}

func mergeSort(nums []int, left, right int) {
    if left >= right {
        return
    }

    mid := left+(right-left)>>1
    mergeSort(nums, left, mid)
    mergeSort(nums, mid+1, right)
    
    merge(nums, left, mid, right)
}

func merge(nums []int, left, mid, right int) {
    i, j, k := left, mid+1, 0
    tmp := make([]int, right-left+1)
    for i <= mid && j <= right {
        if nums[i] < nums[j] {
            tmp[k] = nums[i]
            i++
        }else {
            tmp[k] = nums[j]
            j++
        }
        k++
    }

    for i <= mid {
        tmp[k] = nums[i]
        i++
        k++
    }

    for j <= right {
        tmp[k] = nums[j]
        j++
        k++
    }

    for i:=0; i<len(tmp); i++{
        nums[left+i] = tmp[i]
    }
}

4. References

• Shortest Unsorted Continuous Subarray - LeetCode