Previous Permutation

Given a list of integers, which denote a permutation.

Find the previous permutation in ascending order.

The list may contains duplicate integers.

Example:

For [1,3,2,3], the previous permutation is [1,2,3,3]

For [1,2,3,4], the previous permutation is [4,3,2,1]

Solution:

Similar idea to Next Permutation, but we do it reversely.

Assume we have [1,2,7,1,2,3,6]:

1. We first find the first decreasing trend from the right of the list ( 7 and 1), we choose the index 3 (value is 1).
2. We reverse the elements from index 3 to the end: [1,2,7,1,2,3,6] => [1,2,7,6,3,2,1]
3. If we couldn't find the decreasing trend in step one, we can skip step 3. We may have [1,2,3,4] => [4,3,2,1]
4. We find the first number from index 3 (value is 6 now), where this number should be smaller than the index 2 (value 7) from step 1. Then we swap them: [1,2,7,6,3,2,1] => [1,2,6,7,3,2,1]

Code:

public class Solution {

    public ArrayList<Integer> previousPermuation(ArrayList<Integer> nums) {
        if (nums == null || nums.size() <= 1) {
            return nums;
        }
        int i = nums.size() - 1;
        while (i > 0 && nums.get(i) >= nums.get(i - 1)) {
            i--;
        }
        reverse(nums, i, nums.size() - 1);

        if (i == 0) {
            return nums;
        }

        int j = i;
        while (nums.get(j) >= nums.get(i - 1)) {
            j++;
        }
        swap(nums, j, i - 1);

        return nums;
    }

    private void reverse(List<Integer> nums, int left, int right) {
        for (; left < right; left++, right--) {
            swap(nums, left, right);
        }
    }

    private void swap(List<Integer> nums, int a, int b) {
        int temp = nums.get(a);
        nums.set(a, nums.get(b));
        nums.set(b, temp);
    }
}