LeetCode - Next Permutation

Problem description

description

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

Analysis

Basic idea is to find the first decrease value(v1) from the tail of the array. Then find the first one bigger(v2) than that value(v1). Therefore, we know that the bigger one(v2) should locate in the position of v1 to get the exactly next permutation.

And for the rest of the array from position of v1, we can just rearrange them in increase order.

Here’s the code:

public class NextPermutation {
  public void nextPermutation(int[] nums) {
    for (int i = nums.length - 1; i >= 1; i--) {
      if (nums[i] > nums[i - 1]) {
        int first = i - 1;
        while (i < nums.length && nums[i] > nums[first]) {
          i++;
        }

        i--;
        swap(nums, first, i);
        rearrange(nums, first + 1);
        return;
      }
    }

    rearrange(nums, 0);
  }

  void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
  }

  void rearrange(
      int[] nums, int start) { // already know that the order is decreasing, so just reverse
    Arrays.sort(nums, start, nums.length);
  }
}

From the sample solution in LeetCode, we know that the rest of the array is already in decreasing order, so we can just reverse them.

Here’s the code:

class Solution {
    public void nextPermutation(int[] nums) {
        int i=nums.length-2;
        while(i>=0&&nums[i+1]<=nums[i])
            i--;
        if(i>=0){
            int j=nums.length-1;
            while(j>=0&&nums[j]<=nums[i])
                j--;
            swap(nums,i,j);
        }
        reverse(nums,i+1);
        
}
    private void swap(int [] nums,int i,int j){
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
        
    }
    
    private void reverse(int [] nums, int start){
        int i=start;
        int j=nums.length-1;
        while(i<j){
            swap(nums,i,j);
            i++;
            j--;
        }
    }
}

What to improve

• next permutation is to find a decreasing value from tail. and must remember that the previous path is already proved decreasing.