Next Permutation

Problem statement

Mutate nums into the next arrangement in lexicographic order. If you are already on the last arrangement, wrap around to the sorted ascending sequence.

Example:

Input:

[1, 2, 3]

Expected output:

[1, 3, 2]

Another wrap-around case: [3, 2, 1] becomes [1, 2, 3].

Practice on LeetCode: Next Permutation

Golang Solution

func nextPermutation(nums []int) {
    i := len(nums) - 2
    for i >= 0 && nums[i] >= nums[i+1] {
        i -= 1
    }
    if i >= 0 {
        j := len(nums) - 1
        for nums[j] <= nums[i] {
            j -= 1
        }
        swap(nums, i, j)
    }
    reverse(nums, i+1)
}

func reverse(nums []int, start int) {
    i, j := start, len(nums)-1
    for i < j {
        swap(nums, i, j)
        i++
        j--
    }
}

func swap(nums []int, i int, j int) {
    nums[i], nums[j] = nums[j], nums[i]
}