Finding the Shortest Unsorted Subarray with a Monotonic Stack in Go

LeetCode problem 581 asks for the length of the shortest continuous subarray that, when sorted, makes the whole array sorted.

The solution uses two monotonic stacks to locate the leftmost and rightmost indices of the unsorted segment. In the left‑to‑right pass the stack stores indices in increasing order; whenever a current element is smaller than the top of the stack, the index at the top is popped and the minimal popped index is recorded as the left boundary.

In the right‑to‑left pass the stack stores indices in decreasing order; when a current element is larger than the top, the top index is popped and the maximal popped index becomes the right boundary.

If no indices are popped, the array is already sorted and the answer is 0; otherwise the length is rightIndex - leftIndex + 1.

The full Go implementation is shown below, together with helper min and max functions.

func findUnsortedSubarray(nums []int) int {
    // monotonic stack
    indexStack := []int{}
    leftIndex := len(nums) - 1 // record smallest left index
    rightIndex := 0            // record largest right index

    // left to right, keep increasing order
    for i := 0; i < len(nums); i++ {
        for len(indexStack) != 0 && nums[i] < nums[indexStack[len(indexStack)-1]] {
            leftIndex = min(leftIndex, indexStack[len(indexStack)-1])
            indexStack = indexStack[:len(indexStack)-1]
        }
        indexStack = append(indexStack, i)
    }

    // right to left, keep decreasing order
    indexStack = []int{}
    for i := len(nums) - 1; i >= 0; i-- {
        for len(indexStack) != 0 && nums[i] > nums[indexStack[len(indexStack)-1]] {
            rightIndex = max(rightIndex, indexStack[len(indexStack)-1])
            indexStack = indexStack[:len(indexStack)-1]
        }
        indexStack = append(indexStack, i)
    }

    if leftIndex == len(nums)-1 && rightIndex == 0 {
        // array already sorted
        return 0
    }
    return rightIndex - leftIndex + 1
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

Repository with the solution: https://github.com/gofish2020/leetcode_forever