Golang with detailed explanation/theory for next lexicographic permutation algorithm


  • 0
    A
    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)
    }
    

Log in to reply
 

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