Leetcode 31: Next Permutation

Question

This problem is a bit hard to understand. Suppose we have number 123, then the permutation has 132，213，231，312，321. Sort them in order gives us: 123 132 213 231 312 321. So what we are looking for is 132.

Solution

Solution referenced from here: 31. Next Permutation

In normal cases, to make the number bigger, we need any digit to become larger. If we want to get a number that is just larger than the original one, we need to change the ones digit. For example, change 123 to 124.

Since we are dealing with permutation, we can only exchange the digits.

If we start from the ones digit and proceed from right to left, find a larger one than the ones digit, and exchange them. The ones digit are exchanged to a higher position. After exchange the number become smaller because the ones digit is smaller. For example, number 132, we swap 2 and 3 and get 123, the ones digit become larger, but the overall number becomes smaller.

So ones digit is a no-go. Lets look at tens digti. If we exchange the first larger number that is left to the tens digit, the situation is the same. We will have a smaller number. For example, number 4123, we exchange 2 and 4, get 2143, smaller number!

If for a digit, we proceed from left to right, and exhange a number to the right that is larger. For 4123, we exchange 2 and 3, get 4132 which is larger. If for a certain digit (i.e tens digit), there is no digit to the right that is larger than it, then we move towards left until we get a number that has a digit to the right that is larger.

Another question is what if there are many digits to the right that are larger than it? In this case we want the one that is just larger to make sure the final number is as small as possible.

At this point we have a rough algorithm:

Scan from right to left, find the digit that is smaller than it’s right digit. We make the index of this digit i
Scan from i to end, find the digit that is just larger than i digit. We make the index of this digit j
Exhange i and j

But is it over? No. Although the number is larger, it may not be the next larger number. For example 158476531, we start from tens digit 3, no number to the right of 3 is larger than it. We move to 5, 6, 7, the same. Until 4. Then we look back from, and find 5 that is just larger than 4. Exchange 5 and 4, get 158576431. We have a larger number, but it’s not the one that is just larger. We need to reverse the digits that is right to 5 and get 158513467, which is the just larger number.

Look at the gif from Leetcode might help to understand to process:

Now we have our algorithm:

Scan from right to left, find the first digit that is smaller than it’s right digit

index i
num[i] < num[i+1]

Scan from i to end, find the element that is immediately bigger than nums[i]

index j
From i to end, the order is guaranteed to be descending

Exchange nums[i] and nums[j]
Reverse elements from i + 1 to end

Code:

public void nextPermutation(int[] nums) {
    // start from tens digit
    int firstSmallerIndex = nums.length - 2;

    // find the first element that is smaller than it's right element
    while (firstSmallerIndex >= 0 && nums[firstSmallerIndex + 1] <= nums[firstSmallerIndex]) {
        firstSmallerIndex--;
    }

    // in this case all digit are in descending order (87654321), we just need to reverse all
    if (firstSmallerIndex == -1) {
        reverse(nums, 0);
        return;
    }

    // from firstSmallerIndex to nums.length - 1, it's guaranteed to be in descending order
    // find the index that is just bigger than firstSmallerIndex
    int j = nums.length - 1;
    while (j >= 0 && nums[j] <= nums[firstSmallerIndex]) {
        j--;
    }

    // swap firstSmallerIndex and j
    swap(nums, firstSmallerIndex, j);

    // reverse elements to the right of firstSmallerIndex
    reverse(nums, firstSmallerIndex + 1);
}

// helper method to swap 2 digits in the array
private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

// helper method to reverse all elements starting from start, in the array
private void reverse(int[] nums, int start) {
    int i = start;
    int j = nums.length - 1;

    while (i <= j) {
        swap(nums, i, j);
        i++;
        j--;
    }
}

Time Complexity: the wrost case is to scan all digit, so that is O(n). Space complexity: O(1)

To be honest, I think this question should be a hard level rather than a medium.

Question

Similar Questions

Solution