31.next-permutation.py

#
# @lc app=leetcode id=31 lang=python3
#
# [31] Next Permutation
#
# https://leetcode.com/problems/next-permutation/description/
#
# algorithms
# Medium (37.48%)
# Likes:    14643
# Dislikes: 4068
# Total Accepted:    1M
# Total Submissions: 2.7M
# Testcase Example:  '[1,2,3]'
#
# 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
# 
# 
#

# @lc code=start
class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # 1. Find the largest index k such that nums[k] < nums[k + 1]. If no such index exists, the permutation is the last permutation.
        k = -1
        for i in range(len(nums)-1):
            if nums[i] < nums[i+1]:
                k = i

        # 2. Find the largest index l greater than k such that nums[k] < nums[l].
        if k != -1:
            l = k + 1
            for i in range(k+1, len(nums)):
                if nums[k] < nums[i]:
                    l = i

            # 3. Swap the value of nums[k] with that of nums[l].
            nums[k], nums[l] = nums[l], nums[k]

        # 4. Reverse the sequence from nums[k + 1] up to and including the final element nums[nums.size() - 1].
        nums[k+1:] = nums[k+1:][::-1]

        
# @lc code=end