DATA STRUCTURES • ALGORITHMS

Next Permutation

Rearranging numbers into the lexicographically next greater permutation of numbers. If such an arrangement is not possible, it must rearrange it as the lowest possible order.

Time

O(N)

Space

O(1)

Key Principle 1

Find pivot point from right

Key Principle 2

Find successor of pivot

Key Principle 3

Swap pivot and successor

Key Principle 4

Reverse suffix after pivot

NEXT_PERMUTATION_LAB
ARRAY:
Current Step
Find the next lexicographically greater permutation.
Playback
Pointers ⠿
PIVOT (i)N/A
SUCCESSOR (j)N/A
Algorithm Code ⠿
1int i = n - 2;
2while (i >= 0 && arr[i] >= arr[i+1]) i--;
3if (i >= 0) {
4    int j = n - 1;
5    while (arr[j] <= arr[i]) j--;
6    swap(arr[i], arr[j]);
7}
8reverse(arr, i + 1, n - 1);
1
[0]
2
[1]
3
[2]
6
[3]
5
[4]
4
[5]

Loading Lab...