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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Next Permutation

Number: 31

Difficulty: Medium

Paid? No

Companies: Meta, Google, Amazon, Bloomberg, Microsoft, Uber, Oracle, ServiceNow, HashedIn, DoorDash, Infosys, TikTok, Adobe, Mitsogo, J.P. Morgan, Apple, ByteDance, LinkedIn, Rubrik, Yahoo, DE Shaw

Problem Description

Given an array of integers, rearrange the numbers into the lexicographically next greater permutation. If such arrangement is not possible because the array is in descending order, rearrange it into the lowest possible order (i.e., sorted in ascending order). The replacement must be done in-place with constant extra memory.

Key Insights

  • The problem is solved by identifying the first pair from the right where the left element is less than the right element.
  • Once this pivot is found, find the rightmost element that is greater than this pivot.
  • Swap these two elements.
  • Reverse the subarray that comes after the pivot to ensure the next permutation is the next lexicographically larger sequence.
  • If no such pivot exists, the array is in descending order and should be reversed to get the smallest permutation.

Space and Time Complexity

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

Solution

We start by scanning the array from the right to find the first index (i) such that nums[i] is less than nums[i+1]. This index 'i' represents the pivot point where the next permutation can be formed. If we find such an index, we then scan from the right again to locate the first number that is greater than nums[i] (let this index be j), and swap these two numbers. Finally, we reverse the subarray starting from index i+1 to the end of the array, which gives us the next permutation in lexicographical order. This approach leverages in-place modifications using basic operations like swapping and reversing, thus meeting the constant space requirement.

Code Solutions

def nextPermutation(nums):
    # Length of the array
    n = len(nums)
    # Find the first index from the right where the current number is less than the next number
    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    # If such an index is found, find the number just larger than nums[i] from the right side to swap
    if i >= 0:
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]  # Swap the two numbers
    # Reverse the subarray from i+1 to the end to get the smallest sequence
    left, right = i + 1, n - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

# Example usage:
nums = [1, 2, 3]
nextPermutation(nums)
print(nums)  # Output: [1, 3, 2]
← Back to All Questions