# Finding lexicographically next permutation C++

## Problem Statement

Given array of integers, rearrange the array such that, it becomes lexicographically next greater permutation of numbers i.e. if all the permutations are sorted according to their lexicographical order, then next permutation C++ of the given array is permutation next to the given array in that sorted list of permutations. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

Input: nums = [1,2,3]

Output: [1,3,2]

## Next Permutation C++ Solutions

### Brute Force

#### Algorithm

1. Find every permutation possible for list of given numbers in array
2. Get the just next larger permutation than the given array arrangement.

#### Implementation

```// Next Permutation C++ Solutions: Brute Force

#include <iostream>

#include <vector>

#include <set>

using namespace std;

bool flag = false;
set < vector < int >> allPermutationList;

// Function to get all permutations using backtracking
void permute(vector < int > & A, int l, int r) {
if (l == r) {
allPermutationList.insert(A);

} else {
for (int i = l; i <= r; i++) {
swap(A[l], A[i]);
permute(A, l + 1, r);
if (flag) break;
swap(A[i], A[l]);
}
}
}

// Next Permutation C++ Function
vector < int > nextPermutation(vector < int > nums) {
vector < int > old = nums;

//Get all permutations
permute(nums, 0, nums.size() - 1);

int j = 0;
// iterate through list to get next permutation
for (auto i: allPermutationList) {
// Till the given array is found
if (i == old) {
break;
}
j++;
}
j = j == allPermutationList.size() - 1 ? 0 : j + 1;
nums = * next(allPermutationList.begin(), j);
return nums;
}```

#### Complexity

• Time complexity : O(n!)O(n!). Total possible permutations is n!n!.
• Space complexity : O(n)O(n). Since an array will be used to store the permutations.

### Next Permutation C++ Built In Library

#### Algorithm

C++ provide built in function called next_permutation() which rearranges the object as a lexicographically greater permutation. This function returns true if next greater permutation is possible else returns false to indicate that the arrangement is not greater than the previous, but the lowest possible (sorted in ascending order).

#### Implementation

```// Next Permutation C++ Solutions: Next Permutation C++ Built In Library
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

void nextPermutation(vector<int>& nums) {
next_permutation(nums.begin(), nums.end());
}```

### Efficient Approach

#### Algorithm

1. Find the largest index `k` such that `nums[k] < nums[k + 1]`. If no such index exists, just reverse the array `nums` and return.
2. Find the largest index l such that `l > k` and `nums[k] < nums[l]`.
3. Swap `nums[k]` and `nums[l]`.
4. Reverse the sub-array from index k+l to last (`nums[k + 1:]`).

### Implementation

```// Next Permutation C++ Solutions:

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

vector < int > nextPermutation(vector < int > nums) {
int n = nums.size(), k, l;

// Find largest index such that nums[k] < nums[k + 1]
for (k = n - 2; k >= 0; k--) {
if (nums[k] < nums[k + 1]) {
break;
}
}

// If nothing found reverse the array and return
if (k < 0) {
reverse(nums.begin(), nums.end());
} else {

// Find larger element than nums[k] from right
for (l = n - 1; l > k; l--) {
if (nums[l] > nums[k]) {
break;
}
}
swap(nums[k], nums[l]);
reverse(nums.begin() + k + 1, nums.end());
}
return nums;
}```

#### Complexity

• Time complexity : O(n).
• Space complexity : O(1).

## Conclusion

In this article we discussed various algorithms to find next permutation c++ from brute force to most effective algorithm.

Checkout Minimum Window Substring problem With Detailed Solution here

Got a question or just want to chat? Comment below or drop by our forums, where a bunch of the friendliest people you’ll ever run into will be happy to help you out!

## 90% of Tech Recruiters Judge This In Seconds! 👩‍💻🔍

Don’t let your resume be the weak link. Discover how to make a strong first impression with our free technical resume review!

## Related Articles

### Sum and Difference of Two Numbers HackerRank Solution

Problem Statement The fundamental data types in c are int, float and char. Today, we’re discussing int and float data types. The printf() function prints the given statement to the

### Hello World! in C HackerRank Solution

Problem Statement In this challenge, we will learn some basic concepts of C that will get you started with the language. You will need to use the same syntax to

## Why Aren’t You Getting Interview Calls? 📞❌

It might just be your resume. Let us pinpoint the problem for free and supercharge your job search.