[Solved] Next Permutation -31 C++, Java, Python -Microsoft, Google , Amazon, Media.net

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.

Example 1:

Input: nums = [1,2,3]

Output: [1,3,2]

Example 2:

Input: nums = [3,2,1]

Output: [1,2,3]

Constraints:

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

Solution

Intuition:

The problem requires finding the next permutation in lexicographic order of the given array. If the given permutation is the largest possible permutation, then the function should return the smallest possible permutation by rearranging the array in ascending order.

Approach:

The algorithm finds the first pair of adjacent elements in the array that satisfy nums[k] < nums[k+1] from the right end of the array. If such a pair does not exist, then the entire array is sorted in descending order, and we need to reverse the entire array to obtain the smallest possible permutation.

Otherwise, the algorithm finds the smallest element nums[l] to the right of nums[k] such that nums[l] > nums[k]. We swap nums[k] and nums[l], and then reverse the subarray starting at nums[k+1] to obtain the next lexicographic permutation of the array.

Complexity:

• Time complexity: The algorithm performs two passes over the array. The first pass has time complexity O(n), while the second pass also has time complexity O(n). Therefore, the overall time complexity of the algorithm is O(n).
• Space complexity: The algorithm uses constant extra space, hence the space complexity of the algorithm is O(1).

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size(), k, l;
    	for (k = n - 2; k >= 0; k--) {
            if (nums[k] < nums[k + 1]) {
                break;
            }
        }
    	if (k < 0) {
    	    reverse(nums.begin(), nums.end());
    	} 
        else {
    	    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());
        }
    }
};

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

class Solution(object):
    def nextPermutation(self, nums):
        n = len(nums)
        k, l = n - 2, n - 1
        while k >= 0 and nums[k] >= nums[k + 1]:
            k -= 1
        if k < 0:
            nums.reverse()
        else:
            while l > k and nums[l] <= nums[k]:
                l -= 1
            nums[k], nums[l] = nums[l], nums[k]
            nums[k + 1:n] = reversed(nums[k + 1:n])

Happy Learning – If you require any further information, feel free to contact me.