Find the Next Greater Permutation

In this article, our aim is to solve the problem of finding the next greater permutation for the array containing integers. The next greater permutation is the next larger number that would appear after the current element. Let us understand this through an example:

Example:

Arr = [1,3,4,2]

Output:

Arr = [1,4,2,3]

The next greater number after 1342 is 1423

Solution:

Explanation:

·       We start by iterating through the array from right to left and find where arr[i] becomes smaller than Arr[i+1]. If no such breakpoint exists then ind will remain -1 and reverse.

·       Breakpoint = ind. After this we traverse from right end to ind+1 and swap the first Arr[i] > Arr[ind].

·       Finally reverse(Arr.begin() + ind + 1, Arr.end());

Time Complexity: O(N)

Space Complexity: O(1)