Next Permutation solution leetcode – Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers, 2021

Next Permutation solution leetcode

Next Permutation solution leetcode

Implement next permutation, which rearranges 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 (i.e., sorted in ascending order).

The replacement must be in place and use only constant extra memory.

Next Permutation solution leetcode – Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

Example 1:

Input: nums = [1,2,3]
Output: [1,3,2]

Example 2:

Input: nums = [3,2,1]
Output: [1,2,3]

Example 3:

Input: nums = [1,1,5]
Output: [1,5,1]

Example 4:

Input: nums = [1]
Output: [1]

Next Permutation solution leetcode – Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

Constraints:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 100

Summary

We need to find the next lexicographic permutation of the given list of numbers than the number formed by the given array.Next Permutation solution leetcode – Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

Solution


Approach 1: Brute Force

Algorithm

In this approach, we find out every possible permutation of list formed by the elements of the given array and find out the permutation which is just larger than the given one. But this one will be a very naive approach, since it requires us to find out every possible permutation which will take really long time and the implementation is complex. Thus, this approach is not acceptable at all. Hence, we move on directly to the correct approach.

Complexity Analysis

  • Time complexity : O(n!). Total possible permutations is n!.
  • Space complexity : O(n). Since an array will be used to store the permutations.
    Next Permutation solution leetcode – Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

Approach 2: Single Pass Approach

Algorithm

First, we observe that for any given sequence that is in descending order, no next larger permutation is possible. For example, no next permutation is possible for the following array:

[9, 5, 4, 3, 1]

We need to find the first pair of two successive numbers a[i] and a[i-1], from the right, which satisfy a[i] > a[i-1]. Now, no rearrangements to the right of a[i-1] can create a larger permutation since that subarray consists of numbers in descending order. Thus, we need to rearrange the numbers to the right of a[i-1] including itself.

Now, what kind of rearrangement will produce the next larger number? We want to create the permutation just larger than the current one. Therefore, we need to replace the number a[i-1] with the number which is just larger than itself among the numbers lying to its right section, say a[j].Next Permutation solution leetcode – Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

Next Permutation solution leetcode

We swap the numbers a[i-1] and a[j]. We now have the correct number at index i-1. But still the current permutation isn’t the permutation that we are looking for. We need the smallest permutation that can be formed by using the numbers only to the right of a[i-1]. Therefore, we need to place those numbers in ascending order to get their smallest permutation.

But, recall that while scanning the numbers from the right, we simply kept decrementing the index until we found the pair a[i] and a[i-1] where, a[i] > a[i-1]. Thus, all numbers to the right of a[i-1] were already sorted in descending order. Furthermore, swapping a[i-1] and a[j] didn’t change that order. Therefore, we simply need to reverse the numbers following a[i-1] to get the next smallest lexicographic permutation.

The following animation will make things clearer:

Next Permutation solution leetcode

C++

// Find the next lexicographically
// greater permutation of a word

#include <iostream>

using namespace std;

void swap(char* a, char* b)
{
if (*a == *b)
return;
*a ^= *b;
*b ^= *a;
*a ^= *b;
}
void rev(string& s, int l, int r)
{
while (l < r)
swap(&s[l++], &s[r--]);
}

int bsearch(string& s, int l, int r, int key)
{
int index = -1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (s[mid] <= key)
r = mid - 1;
else {
l = mid + 1;
if (index == -1 || s[index] >= s[mid])
index = mid;
}
}
return index;
}

bool nextpermutation(string& s)
{
int len = s.length(), i = len - 2;
while (i >= 0 && s[i] >= s[i + 1])
--i;
if (i < 0)
return false;
else {
int index = bsearch(s, i + 1, len - 1, s[i]);
swap(&s[i], &s[index]);
rev(s, i + 1, len - 1);
return true;
}
}

// Driver code
int main()
{
string s = { "gfg" };
bool val = nextpermutation(s);
if (val == false)
cout << "No Word Possible" << endl;
else
cout << s << endl;
return 0;
}
// This code is contributed by Mysterious Mind

Next Permutation solution leetcode – Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

Complexity Analysis

  • Time complexity : O(n). In worst case, only two scans of the whole array are needed.
  • Space complexity : O(1). No extra space is used. In place replacements are done.

Next Permutation solution leetcode – Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

Next Permutation solution leetcode

Next Permutation solution leetcode – Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

Also read : Minimum Interval to Include Each Query solution leetcode


Leave a Comment