{x}
blog image

Next Permutation

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]

Example 3:

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

 

Constraints:

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

31. Next Permutation

Problem Description

Given an array of integers nums, find the next lexicographically greater permutation of nums. If such an arrangement is not possible, the array must be rearranged as the lowest possible order (ascending order). The solution must be in-place and use only constant extra memory.

Solution Explanation

The solution utilizes a two-pass approach to efficiently find the next permutation:

Pass 1: Find the pivot

The algorithm iterates through the array from right to left, searching for the first index i where nums[i] < nums[i + 1]. This index i represents the pivot point – the element that needs to be swapped to create the next permutation. If no such index is found (the array is in descending order), it means the next permutation is the smallest possible permutation (ascending order).

Pass 2: Find the swap element and reverse

  1. If a pivot i is found, the algorithm iterates from right to left again to find the smallest element nums[j] that is greater than nums[i].
  2. nums[i] and nums[j] are swapped.
  3. Finally, the subarray from nums[i + 1] to the end of the array is reversed to obtain the next lexicographical permutation.

If no pivot is found (array is already in descending order), the entire array is reversed to produce the ascending order.

Time and Space Complexity

  • Time Complexity: O(n) - The algorithm performs two linear scans of the array, resulting in a linear time complexity. Reversing the subarray is also a linear operation.
  • Space Complexity: O(1) - The algorithm operates in-place, using only a constant amount of extra space for variables.

Code Implementation (Python)

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        n = len(nums)
        i = n - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1
 
        if i >= 0:
            j = n - 1
            while j > i and nums[j] <= nums[i]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]
 
        left = i + 1
        right = n - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

This Python code directly implements the two-pass approach. The while loops efficiently find the pivot and swap element. The while left < right loop reverses the relevant subarray using simultaneous assignment.

Code Implementation in other languages (brief overview)

The core logic remains consistent across different programming languages. The provided solutions demonstrate this in Java, C++, Go, TypeScript, JavaScript, C#, and PHP. The variations mainly involve syntax and function/method naming conventions of each language. For example, array reversal might be achieved using built-in functions like reverse() (C++, Python) or manual iteration and swapping. Swapping elements might involve helper functions or direct use of assignment within the languages' syntax. All maintain the O(n) time and O(1) space complexity.