# Golang with detailed explanation/theory for next lexicographic permutation algorithm

• ``````func nextGreaterElement(n int) int {
b := []byte(strconv.Itoa(n))
if len(b) < 2 {
return -1
}

// We want the minimal increment, which means that we want to touch the right-most (least-significant) digits of n possible
// The theory here is that we want to find the largest prefix of the digits of n that we can hold constant
// If we have to change a certain digit at position j, then only 0..(j-1) can be held constant
// When are we forced to change the digit at position j?
// When the digits j+1... are descending, e.g. 934553321 => j = 2 (n[2]=4), because 553321 is descending
// Why descending? because there is no greater permuation that all the given elements in desending order

var j, k int
for j = len(b) - 2; j >= 0 && b[j] >= b[j+1]; j-- { // Find j such that the previous digits are descending
}
if j == -1 { // If we exit the loop without finding j, that means that n is already the final (totally descending) permutation
return -1
}

// Ok, we we've found j, how do we know how to change j?
// Well, we need to find the smallest number to the right of j that's bigger than j, then swap
// Remember that j+1... is in sorted (descending) order, so it is simple to find such a position k

for k = len(b) - 1; k > j && b[j] >= b[k]; k-- { // Find a k such that b[k] > b[j]
}
b[j], b[k] = b[k], b[j] // Swap them

// Okay, so now our number is bigger than before, but is it the smallest such number?
// The smallest such number will reorder the digits j+1... to be in ascending order
// I'll let you work it out that these digits are still sorted at this moment, even after the j/k swap
// So we just need to reverse from j+1 to the end

for j, k = j+1, len(b)-1; j < k; j, k = j+1, k-1 { // Reverse j+1 to the end
b[j], b[k] = b[k], b[j]
}

m, err := strconv.ParseInt(string(b), 10, 32) // Now we have to verify that we can fit this in 32 bits
if err != nil {
return -1
}
return int(m)
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.