# Previous Permutation

## Problem

Given a list of integers, which denote a permutation.

Find the previous permutation in ascending order.

Notice: 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]

## Code - Java

public class Solution {
/**
* @param nums: A list of integers
* @return: A list of integers that's previous permuation
*/
public ArrayList<Integer> previousPermuation(ArrayList<Integer> nums) {

int len = nums.size();
ArrayList<Integer> result = new ArrayList<>(len);
int i;
for (i = len - 1; i > 0 && nums.get(i) >= nums.get(i - 1); i--) ;
int j = i - 1;

if (j < 0) {
reverse(nums, 0, len - 1);
} else {
int k = len - 1;
while (nums.get(k) >= nums.get(j)) k--;

int tmp = nums.get(j);
nums.set(j, nums.get(k));
nums.set(k, tmp);

reverse(nums, i, len - 1);
}

return nums;
}

private void reverse(ArrayList<Integer> nums, int i, int j) {
while (i < j) {
int tmp = nums.get(i);
nums.set(i, nums.get(j));
nums.set(j, tmp);
i++;
j--;
}
}
}