Next Permutation

Given a sequence of numbers, find the lexicographically next greater permutation of that sequence. This problem is a classic interview question and has applications in areas like sorting algorithms and combinatorial optimization. The goal is to modify the input array in-place to represent the next permutation, or if no such permutation exists, sort the array in ascending order.

Problem Description

You are given an integer array nums. Your task is to rearrange the elements of nums in-place to produce the lexicographically next greater permutation. If no such permutation exists (i.e., the array is already in descending order), you must sort the array in ascending order.

What needs to be achieved:

• Find the next greater permutation of the input array nums.
• Modify the array nums in-place – you cannot create a new array.
• If no next greater permutation exists, sort nums in ascending order.

Key Requirements:

• The permutation must be the next lexicographically greater one.
• The solution must be efficient, considering the constraints.
• The solution must modify the input array directly.

Expected Behavior:

The function should return None (or its language equivalent, indicating no return value) as the modification is done in-place.

Edge Cases to Consider:

• Arrays with a single element.
• Arrays that are already in descending order.
• Arrays with duplicate elements.
• Arrays with all elements being the same.

Examples

Example 1:

Input: [1, 2, 3]
Output: [1, 3, 2]
Explanation: The next permutation of [1, 2, 3] is [1, 3, 2].

Example 2:

Input: [3, 2, 1]
Output: [1, 2, 3]
Explanation: Since [3, 2, 1] is the largest permutation, the next permutation is the smallest, which is [1, 2, 3].

Example 3:

Input: [1, 1, 5]
Output: [1, 5, 1]
Explanation: The next permutation of [1, 1, 5] is [1, 5, 1].

Example 4:

Input: [1]
Output: [1]
Explanation: A single-element array remains unchanged.

Constraints

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100
• The solution should ideally have a time complexity of O(n) where n is the length of the input array.
• The solution must modify the input array in-place, using O(1) extra space.

Notes

A common approach involves finding the largest index i such that nums[i] < nums[i+1]. Then, find the largest index j > i such that nums[j] > nums[i]. Swap nums[i] and nums[j]. Finally, reverse the subarray from i+1 to the end of the array. If no such i is found, the array is in descending order, and you need to sort it. Consider how to handle duplicate elements efficiently.