31.next-permutation.md

31. Next Permutation

• Nice explanation: https://leetcode.com/problems/next-permutation/solutions/13867/c-from-wikipedia/comments/14266
• With Diagram: https://leetcode.com/problems/next-permutation/solutions/13994/readable-code-without-confusing-i-j-and-with-explanation/

fun nextPermutation(nums: IntArray): Unit {
    var firstNonIncreasingIndex: Int? = null
    for (i in nums.size - 2 downTo 0) {
        if (nums[i] < nums[i + 1]) {
            firstNonIncreasingIndex = i
            break
        }
    }
    if (firstNonIncreasingIndex == null) {
        reverseArray(nums, 0, nums.size - 1)
        return
    }

    for (i in nums.size - 1 downTo 0) {
        if (nums[i] > nums[firstNonIncreasingIndex!!]) {
            nums.swap(i, firstNonIncreasingIndex)
            reverseArray(nums, firstNonIncreasingIndex + 1, nums.size - 1)
            break    
        }
    }
}

private fun reverseArray(nums: IntArray, start: Int, end: Int) {
    var left = start
    var right = end
    while (left < right) {
        nums.swap(left, right)
        left++
        right--
    }
}

private fun IntArray.swap(i: Int, j: Int) {
    val temp = this[i]
    this[i] = this[j]
    this[j] = temp
}