Leetcode 31: Next Permutation

CATEGORY: MEDIUM

Problem

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

For example, the next permutation of arr = [1,2,3] is [1,3,2].
Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.

Given an array of integers nums, find the next permutation of nums.

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

Examples

First Example :

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

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

Second Example:

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

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

Third Example:

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

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

Constraints:

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

Solution Approach

Solution Logic

In this problem of Next Permutation, we need to find the next number which comes in the sequence. Finding the next greater number can be a tricky problem to solve efficiently. One way to approach this is to scan the array from the back towards the front. When we find an element that is smaller than its right element(s). We know that this location needs to be updated with a greater element. We can call this index “i”. However, we don’t want any element that is just greater; we want the smallest element among all the potential candidates. To find this, we scan again from the back and locate that element, and swap it with index i. Once we have the correct element at index i, we can make the remaining elements in ascending order by reversing.

This algorithm has a time complexity of O(n) and a space complexity of O(1). By scanning the array from the back, we can minimize the number of comparisons needed to find the next greater number, making it an efficient approach.

Code Logic

This code is implementing the “next permutation” algorithm for an array of integers. Here’s how it works:

The input array is passed to the nextPermutation() method.
The variable “i” is initialized to the second-to-last index of the array.
A while loop is used to check if “i” is greater than or equal to 0 AND if the element at index “i” is greater than or equal to the element at index “i+1”. If both conditions are true, then “i” is decremented by 1.
If “i” is still greater than or equal to 0, then another variable “j” is initialized to the last index of the array.
Another while loop is used to check if “j” is greater than or equal to 0 AND if the element at index “j” is less than or equal to the element at index “i”. If both conditions are true, then “j” is decremented by 1.
After finding the correct values of “i” and “j”, the swap() method is called to swap the elements at index “i” and index “j”.
Finally, the reverse() method is called to reverse the elements from index “i+1” to the end of the array.

In summary, the nextPermutation() method uses two helper methods, swap() and reverse(), to modify the input array in place and generate the next lexicographically greater permutation of the array.

Helper Methods

swap(int[] nums, int i, int j):

This method takes three parameters: an array of integers “nums”, and two indices “i” and “j”.
It swaps the elements at index “i” and index “j” in the array.
It achieves this by creating a temporary variable “tmp” to hold the value at index “i”.
It then sets the value at index “i” to be the value at index “j”.
Finally, it sets the value at index “j” to be the value in the temporary variable “tmp”.

reverse(int[] nums, int start):

This method takes two parameters: an array of integers “nums”, and a starting index “start”.
It reverses the elements in the array from index “start” to the end of the array.
It achieves this using a while loop that runs as long as the “start” index is less than the end index.
Inside the loop, it calls the swap() method to swap the elements at index “start” and the corresponding index at the end of the array.
After each iteration of the loop, it increments the “start” index and decrements the end index until the two indices cross each other in the middle of the array.
The result is that the elements in the array from index “start” to the end of the array are reversed.

Solution Code

class Solution {
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i+1]) i--;
        if (i >= 0){
            int j = nums.length - 1;
            while(j >= 0 && nums[j] <= nums[i]) j--;
            swap(nums, i, j);
        }
        reverse(nums, i + 1);
    }

    public void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    public void reverse(int[] nums, int start){
        int end = nums.length -1;
        while(start < end){
            swap(nums, start++, end--);
        }
    }
}

class Solution {

public void nextPermutation(int[] nums) {

int i = nums.length - 2;

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

if (i >= 0){

int j = nums.length - 1;

while(j >= 0 && nums[j] <= nums[i]) j--;

swap(nums, i, j);

}

reverse(nums, i + 1);

}

public void swap(int[] nums, int i, int j){

int tmp = nums[i];

nums[i] = nums[j];

nums[j] = tmp;

}

public void reverse(int[] nums, int start){

int end = nums.length -1;

while(start < end){

swap(nums, start++, end--);

}

For more Leetcode explained solutions visit Leetcode Solutions. If you like capture the flag challenges visit here.

Check out my socials below in the footer. Feel free to ask any doubts in the comment section or contact me via the Contact page. Happy Leetcoding 🙂