We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Next Permutation

Difficulty: Medium

Problem Description

Given an array of integers nums, find the next permutation of nums in lexicographical order. The replacement must be in place and use only constant extra memory.

Key Insights

  • A permutation is an arrangement of elements in a specific order.
  • The next permutation is the next lexicographically greater arrangement of the array.
  • If the array is in descending order, the next permutation is the lowest possible order (sorted in ascending).
  • The algorithm involves identifying the rightmost ascent and swapping it with the next higher element to its right.

Space and Time Complexity

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

Solution

The algorithm uses the following steps:

  1. Traverse the array from the end to find the first pair where nums[i] < nums[i + 1]. This identifies the rightmost ascent in the array.
  2. If such a pair is found, traverse again from the end to find the smallest element that is larger than nums[i] to swap with.
  3. Swap these two elements.
  4. Reverse the sequence after the original position of i to get the next permutation.
  5. If no ascent is found, it means the array is sorted in descending order, so we simply reverse the entire array.

Code Solutions

def next_permutation(nums):
    n = len(nums)
    i = n - 2
    
    # Step 1: Find the rightmost ascent
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
        
    if i >= 0:
        # Step 2: Find the element just larger than nums[i] to swap with
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]  # Swap
    
    # Step 3: Reverse the sequence after i
    nums[i + 1:] = reversed(nums[i + 1:])
← Back to All Questions