Next Permutation

Time: O(n)

Space: O(1)

Intuition

Three steps: (1) find the rightmost "descent" (arr[i] < arr[i+1]). (2) Swap arr[i] with the smallest element greater than arr[i] to its right. (3) Reverse the suffix after position i to get the next smallest permutation.

Algorithm

1Find i from n-2 down: first index where arr[i] < arr[i+1]. If none: reverse all (last permutation).
2Find j from n-1 down: first index where arr[j] > arr[i]. Swap arr[i] and arr[j].
3Reverse arr[i+1..n-1].

Example Walkthrough

Input: arr = [1,2,3]

1.i=1 (arr[1]=2 < arr[2]=3). j=2 (arr[2]=3 > 2). Swap: [1,3,2]. Reverse suffix: [1,3,2]. â†’ [1,3,2].

Output: [1,3,2]

Common Pitfalls

•Reverse the suffix, do not sort it â€” the suffix is already in descending order so reversing achieves ascending order in O(n).

Next Permutation.java

Java

// Approach: Find rightmost ascent from right, find next larger element right of it, swap, reverse suffix.
// Time: O(n) Space: O(1)
class Solution {
    void nextPermutation(int[] arr) {
        int i, n = arr.length;
        for (i = n - 2; i >= 0; i--) {
            if (arr[i] < arr[i + 1])
                break;
        }
        if (i > -1) {
            int nextMax = Integer.MAX_VALUE, nextPos = 0;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] > arr[i] && arr[j] < nextMax) {
                    nextMax = arr[j];
                    nextPos = j;
                }
            }
            int tmp = arr[i];
            arr[i] = arr[nextPos];
            arr[nextPos] = tmp;
            reverse(arr, i + 1, n - 1);
        } else
            reverse(arr, 0, n - 1);
    }

    void reverse(int[] arr, int i, int j) {
        while (i < j) {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
            j--;
        }
    }
}

Was this solution helpful?