LeetCode: Previous Permutation With One Swap

Posted on June 18, 2019July 26, 2020 by braindenny

Previous Permutation With One Swap

Similar Problems:

Given an array A of positive integers (not necessarily distinct), return the lexicographically largest permutation that is smaller than A, that can be made with one swap (A swap exchanges the positions of two numbers A[i] and A[j]). If it cannot be done, then return the same array.

Example 1:

Input: [3,2,1]
Output: [3,1,2]
Explanation: Swapping 2 and 1.

Example 2:

Input: [1,1,5]
Output: [1,1,5]
Explanation: This is already the smallest permutation.

Example 3:

Input: [1,9,4,6,7]
Output: [1,7,4,6,9]
Explanation: Swapping 9 and 7.

Example 4:

Input: [3,1,1,3]
Output: [1,3,1,3]
Explanation: Swapping 1 and 3.

Note:

1 <= A.length <= 10000
1 <= A[i] <= 10000

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution: To find the candidate, loop from the l[left] to right

// https://code.dennyzhang.com/previous-permutation-with-one-swap
// Basic Ideas: next permutation
//
//  Like next permutation
//
//  The later the digit is, the smaller change it would be
//
//  From right to left, find the longest non-increasing subarray
//  For the previous element, find the biggest value which is smaller than it.
//  If there is a tie, find the first one
//    Do the swap
//
// Complexity: Time O(n), Space O(n)
func prevPermOpt1(A []int) []int {
    i := len(A)-1
    for ; i-1>=0 && A[i-1]<=A[i]; i-- {
    }
    // Current one is the smallest, can't find a candidate.
    if i == 0 {
        return A
    }
    // find the biggest value to swap
    j := i
    for ; j+1<len(A) && A[j+1]<A[i-1]; j++ {

    }
    // When there is a tie, get the first one
    for ; j-1>=0 && A[j-1] == A[j]; j-- {

    }
    A[i-1], A[j] = A[j], A[i-1]
    return A
}

Solution: To find the candidate, loop from l[len(l)-1] to left

// https://code.dennyzhang.com/previous-permutation-with-one-swap
// Basic Ideas: next permutation
//
//  Like next permutation
//
//  The later the digit is, the smaller change it would be
//
//  From right to left, find the longest non-increasing subarray
//  For the previous element, find the biggest value which is smaller than it.
//  If there is a tie, find the first one
//    Do the swap
//
// Complexity: Time O(n), Space O(n)
func prevPermOpt1(A []int) []int {
    i := len(A)-1
    for ; i-1>=0 && A[i-1]<=A[i]; i-- {
    }
    // Current one is the smallest, can't find a candidate.
    if i == 0 {
        return A
    }
    left := i-1
    // find the biggest smaller value to swap
    right := len(A)-1
    for ; A[right] >= A[left]; right-- {

    }
    // When a tie, find the first one
    for ; A[right-1] == A[right]; right-- {

    }
    A[left], A[right] = A[right], A[left]
    return A
}

Post Views: 0