LeetCode. 31. Next Permutation

[Link] https://leetcode.com/problems/next-permutation/

Approach

To obtain the smallest permutation that is still greater than the current one, change the rightmost position that can be increased. Scan from right to left for the first index i where nums[i] < nums[i + 1]. The suffix after i is nonincreasing; if no such index exists, the entire array is nonincreasing and is already the greatest permutation, so reverse it to get the smallest order.

When a pivot exists, find the rightmost suffix value greater than nums[i] and swap them. The suffix’s nonincreasing order means this rightmost greater value is the smallest value that can replace the pivot while making the whole number larger. Reverse the suffix to put its values in increasing order, producing the smallest possible remainder.

The algorithm runs in O(N) time and uses O(1) extra space.

Java

class Solution {
    public void nextPermutation(int[] nums) {
        int pivot = nums.length - 2;
        while (pivot >= 0 && nums[pivot] >= nums[pivot + 1]) {
            pivot--;
        }

        if (pivot >= 0) {
            int successor = nums.length - 1;
            while (nums[successor] <= nums[pivot]) {
                successor--;
            }
            swap(nums, pivot, successor);
        }

        reverse(nums, pivot + 1, nums.length - 1);
    }

    private void reverse(int[] nums, int left, int right) {
        while (left < right) {
            swap(nums, left++, right--);
        }
    }

    private void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}