Untitled

 avatar
unknown
plain_text
a year ago
1.3 kB
8
Indexable
from collections import Counter

class Solution:
    def isPermutationValid(self, permutation, frequencyMap):
        for num, value in Counter(permutation).items():
            if num not in frequencyMap:
                return False
            if value != frequencyMap[num]:
                return False
        return True

    def moveByOne(self, nums: List[int], numToIndexMap, indexToNumMap) -> List[int]:
        position = len(nums) - 1
        while position >= 0:
            num = nums[position]
            indexInMap = numToIndexMap[num]
            if indexInMap == len(numToIndexMap) - 1:
                nums[position] = indexToNumMap[0]
                position -= 1
            else:
                nums[position] = indexToNumMap[indexInMap + 1]
                return


    def nextPermutation(self, nums: List[int]) -> None:
        frequencyMap = Counter(nums)
        numToIndexMap = {}
        indexToNumMap = {}
        uniqueElements = list(set(nums))
        for index, num in enumerate(uniqueElements):
            numToIndexMap[num] = index
            indexToNumMap[index] = num

        self.moveByOne(nums, numToIndexMap, indexToNumMap)
        while not self.isPermutationValid(nums, frequencyMap):
            self.moveByOne(nums, numToIndexMap, indexToNumMap)


        
Editor is loading...
Leave a Comment