Finding the Next Lexicographically Greater Permutation

Problem

Given an input sequence in the form of an array, the task is to rearrange the elements into the lexicographically next greater permutation if it exists, or return the lexicographically smallest permutation otherwise.

LeetCode Problem Link

We’ll explore two approaches to solve this problem: one using the C++ STL inbuilt next_permutation() method, and the other using an efficient algorithm.

Example

nums[] = [1, 2, 3]

The permutations of the above array nums[] in lexicographical order will be:

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
[1, 2, 3]
...

Approach I (Using C++ STL next_permutation())

The C++ Standard Template Library (STL) provides a convenient method called next_permutation() which rearranges the elements of a sequence into the lexicographically next greater permutation if it exists. This method operates in-place and returns true if the next permutation exists, and false otherwise.

next_permutation() method is available in C++ <algorithm> header. Its time complexity is O(n). You could read more about it here.

Code Implementation

//
//  main.cpp
//  Next Permutation (using STL)
//
//  Created by Himanshu on 20/03/24.
//

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;


void printNextPermutation(vector<int>& nums) {
    
    if (next_permutation(nums.begin(), nums.end())) {
        cout << "Next Permutation: " << endl;
    } else {
        cout << "No next permutation exists. Returning the smallest permutation:"
        << endl;
    }
    
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;
}

int main() {
    vector<int> nums = {1, 2, 3};
    
    cout << "Original Permutation: ";
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;
    
    printNextPermutation(nums);
    
    return 0;
}

Output

Original Permutation: 1 2 3 
Next Permutation: 
1 3 2 

Time Complexity: O(n), n is the size of input array
Space Complexity: O(1)

Approach II

The efficient method to find the next lexicographically greater permutation involves three main steps:

1. Find the largest index i such that nums[i] < nums[i+1].
2. Find the largest index j greater than i such that nums[i] < nums[j].
3. Swap elements at indices i and j, and reverse the subarray from index i+1 to the end.

This method performs better than the C++ STL method on LeetCode.

Pseudocode

nextPermutation(nums):
    n = length of nums
    i = n - 2

    while i >= 0 and nums[i] >= nums[i + 1]:
        i--

    if i >= 0:
        j = n - 1
        while j >= 0 and nums[i] >= nums[j]:
            j--
        swap(nums[i], nums[j])

    reverse(nums.begin() + i + 1, nums.end())

Code Implementation

//
//  main.cpp
//  Next Permutation
//
//  Created by Himanshu on 20/03/24.
//

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;


void nextPermutation(vector<int>& nums) {
    int n = (int) nums.size();
    int i = n - 2;

    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }

    if (i >= 0) {
        int j = n - 1;
        while (j >=0 && nums[j] <= nums[i]) {
            j--;
        }
        
        swap(nums[i], nums[j]);
    }

    reverse(nums.begin() + i + 1, nums.end());
}


int main() {
    vector<int> nums = {1, 2, 3};
    
    cout << "Original Permutation: ";
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;
    
    nextPermutation(nums);
    
    cout << "Next Permutation: ";
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;
    
    return 0;
}

Output

Original Permutation: 1 2 3
Next Permutation: 1 3 2

Time Complexity: O(n), n is the size of input array
Space Complexity: O(1)

While C++ STL next_permutation() method is more concise and convenient to use, the Approach II algorithm is slightly more complex. However, second approach offers better control and understanding of the permutation process which can be more suitable for scenarios where customization is required.