Next Greater Permutation Editorial

Practice Problem Link: Next Greater Permutation | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given an array, rearrange it to its next greater permutation. Do it in-place with extra constant memory only. Do not use any library function for the next permutation.

Naive Approach

The naive approach here will be a straight brute force. Find all the permutations of the given array, find the current permutation, and then print the next permutation in the list

Analysis

• Time Complexity: O(n * n!) or O(n * n! * log(n!)) depending on implementation.
• Space Complexity: O(n) 

Optimal Approach

We can solve this problem in a single pass.

• First, observe that if the array is sorted in descending order, no next greater permutation is possible for the array, so we just reverse the array and return it.
• Else, traverse the array from right to left, and find the first position where a[i] > a[i - 1].
• We can observe that we need to reverse numbers to the right of a[i - 1] for the next greater permutation.
• How can we get the next greater permutation? Well, observe that the next greater permutation will have the element just greater than a[i - 1] to the right of a[i - 1] swapped with a[i - 1].
• Now, just reverse the subarray from a[i] to the end of the array to get the next greater permutation.

Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Implementation

C++

void nextGreaterPermutation(vector<int> &arr) {
   reverse(arr.begin(), arr.end());
   if (isSorted(arr.begin(), arr.end())) {
       return;
   }
   int index = 0;
   for (int i = 1; i < arr.size(); i++) {
       if (arr[i - 1] > arr[i]) {
           index = i;
           break;
       }
   }
   for (int i = 0; i < index; i++) {
       if (arr[i] > arr[index]) {
           swap(arr[i], arr[index]);
           break;
       }
   }
   reverse(arr.begin(), arr.begin() + index);
   reverse(arr.begin(), arr.end());
}

Java

class Solution {
   void nextGreaterPermutation (int[] arr) {
       reverse(arr, 0, arr.length - 1);
       if (isSorted(arr) == true) {
           return;
       }
       int index = 0;
       for (int i = 1; i < arr.length; i++) {
           if (arr[i - 1] > arr[i]) {
               index = i;
               break;
           }
       }
       for (int i = 0; i < index; i++) {
           if (arr[i] > arr[index]) {
               swap(arr, i, index);
               break;
           }
       }
       reverse(arr, 0, index - 1);
       reverse(arr, 0, arr.length - 1);
   }
   boolean isSorted(int[] arr) {
       boolean sorted = true;
       for(int i = 1; i < arr.length; i++) {
           if(arr[i] < arr[i - 1]) {
               sorted = false;
           }
       }
       return sorted;
   }
   void reverse(int[] arr, int start, int end) {
       int left = start, right = end;
       while(left < right) {
           swap(arr, left, right);
           left++;
           right--;
       }
   }
   
   void swap(int[] arr, int first, int second) {
       int temp = arr[first];
       arr[first] = arr[second];
       arr[second] = temp;
   }
}