class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        """
        if strictly descending, reverse and return

        3 1 2 -> 3 2 1
        3 1 4 -> 3 4 1
        2 4 0 -> 4 0 2
        2 4 0 3 -> 2 4 3 0
        2 4 3 0 -> 3 0 2 4
        2 9 1 1 -> 9 1 1 2
        2 1 3 0 -> 2 3 0 1

        starting from right
        first time the next val is less than the current val:
        swap current val and next val
        sort rest of list from least to greatest
        doesn't work -- 2 4 3 0 would be 4 0 2 3, should be 3 0 2 4

        find the last descending run -- for 2 4 3 0 would be "4 3 0"
        look at next number -- for 2 4 3 0 woul dbe "2"
        find the first number greater than "2", would be "3"
        swap the "next" and "first greater" number
        sort the indices of the last descending run, ascending
        if there is no first greater number:
        """

        ptr = len(nums) - 1

        while ptr > 0:
            next_ptr = ptr - 1
            if nums[next_ptr] < nums[ptr]:
                # the longest run is from ptr to the end of the array
                # the longest run is from greatest to least, left to right
                # we want to find the first value, from right to left, that is
                # greater than nums[ptr_next]
                target = nums[next_ptr]
                # TODO: maybe use some kind of binary search here instead
                # bisect doesn't deal with reverse-order lists :(
                # maybe reverse the list with [::-1]
                target_idx = len(nums) - 1
                while nums[target_idx] <= target:
                    target_idx -= 1
                # nums[target_idx] is the first number greater than target
                # we want to swap nums[next_ptr] and nums[target_idx]
                nums[next_ptr], nums[target_idx] = nums[target_idx], nums[next_ptr]
                # now sort the rest of the list
                break
            ptr -= 1
        # we looked at the whole array and it's all strictly descending
        # reverse the whole thing
        nums[ptr:] = sorted(nums[ptr:])