#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/google-interview-prep-v2/coding-patterns-i-arrays-strings-hash-maps/lc-31-next-permutation-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/google-interview-prep-v2/coding-patterns-i-arrays-strings-hash-maps/lc-31-next-permutation-implementation

Repovive

LeetCode 31 Next Permutation - Implementation - Coding Patterns I: Arrays, Strings & Hash Maps | Google Interview Prep | Repovive

Repovive.

Google Interview Prep6 sections · 128 units7h total

Open in Course

LeetCode 31 Next Permutation - Implementation

The code

Find the pivot, swap with the next-larger element, reverse the suffix.

function nextPermutation(nums):
    n = len(nums)
    pivot = -1
    for i from n-2 down to 0:
        if nums[i] < nums[i+1]:
            pivot = i
            break
    if pivot == -1:
        reverse(nums, 0, n-1)
        return
    for j from n-1 down to pivot+1:
        if nums[j] > nums[pivot]:
            swap(nums[pivot], nums[j])
            break
    reverse(nums, pivot+1, n-1)

function reverse(arr, lo, hi):
    while lo < hi:
        swap(arr[lo], arr[hi])
        lo += 1
        hi -= 1

$O(n)$ time, $O(1)$ space.