algoadvance

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 to the lowest possible order (i.e., sorted in ascending order).

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

Example:

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

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

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

Clarifying Questions

  1. Will the input array always contain integers?
    • Yes.
  2. Can the input array be empty?
    • No, the input array will always have at least one element.
  3. Are there any constraints on the size of the input array?
    • The problem specifies the need to rearrange the array in-place and using constant extra memory, so performance considerations usually imply the input array can be large.

Strategy

  1. Identify the Break Point:
    • Traverse the array from the end to find the first element that is smaller than the element next to it (nums[i] < nums[i + 1]). This is the element that needs to be changed to get the next permutation. Let’s call this index i.
  2. Special Case If No Break Point:
    • If no such element is found, this means the array is sorted in descending order. In this case, reverse the entire array to get the smallest permutation.
  3. Find the Smallest Larger Element:
    • From the end of the array, find the element that is just larger than nums[i]. This element will be swapped with nums[i]. Let’s call this index j.
  4. Swap and Reverse:
    • Swap nums[i] and nums[j].
    • Reverse the sub-array from index i+1 to the end of the array to get the next lexicographically smallest permutation.

Code

def nextPermutation(nums):
    n = len(nums)
    if n <= 1:
        return
    
    # Step 1: Find the first decreasing element from the end
    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    
    # Step 2: If no decreasing element is found, reverse the whole array
    if i == -1:
        nums.reverse()
        return
    
    # Step 3: Find the element just larger than nums[i] to swap with
    j = n - 1
    while nums[j] <= nums[i]:
        j -= 1
    
    # Step 4: Swap elements at i and j
    nums[i], nums[j] = nums[j], nums[i]
    
    # Step 5: Reverse the sub-array from i+1 to the end
    nums[i + 1:] = reversed(nums[i + 1:])

# Example Usage:
nums = [1, 2, 3]
nextPermutation(nums)
print(nums)  # Output: [1, 3, 2]

Time Complexity

Try our interview co-pilot at AlgoAdvance.com