Leetcode: Next Permutation

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, do not allocate 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

Understand the problem:
The problem is a little a bit harder to understand. So you must first understand what is the lexicographical order. Basically, the lexicographic or lexicographical order (also known as lexical order, dictionary order, alphabetical order or lexicographic(al) product) is a generalization of the way the alphabetical order of words is based on the alphabetical order of their component letters.

The next permutation means the next greater permutation of numbers according to the lexicographical order. For example, for the input 1 2 3, its permutations according to the lexicographical order is
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
So its next permutation is 1 3 2. Since list in decreasing order is already the greatest, its next available permutation will be wrapped around to 1 2 3.

Solution:
Since we know at for a words in ascending order must be the smallest lexicographical order, while in descending order is the greatest lexicographical order. 

So we can iterate through the input string from end in reverse order, and find the first descending number. Mark that index. Then scan through the numbers after the number we found, until we find the smallest number which is still greater than the number we found. Since the string after the number is in descending order, it is pretty easy to find this number. We then swap this numbers. At least, we make all numbers behind the first number we found as in ascending order. 

Code (Java):

public class Solution {
    public void nextPermutation(int[] num) {
        if (num == null || num.length == 0) {
            return;
        }
        
        int i, j;
        for (i = num.length - 2; i >= 0; i--) {
            if (num[i] < num[i + 1]) {
                break;
            }
        }
        
        // for the case where the num[] is in descending order
        if (i >= 0) {
            for (j = i + 1; j < num.length; j++) {
                if (num[j] <= num[i]) {
                    break;
                }
            }
            j = j - 1;
            swap(num, i, j);
        }
        reverse(num, i + 1);
    }
    
    private void swap(int[] num, int i, int j) {
        int temp = num[i];
        num[i] = num[j];
        num[j] = temp;
    }
    
    private void reverse(int[] num, int start) {
        int end = num.length - 1;
        while (start < end) {
            int temp = num[start];
            num[start] = num[end];
            num[end] = temp;
            
            start++;
            end--;
        }
    }
}

Discussion:
We scan the array three times, so the time complexity is still O(n). Space complexity is O(1) since we don't use additional space. 

Summary:
The crux of the problem is to figure out what is the lexicographical order. After we know this, we scan from the end in reverse order. We scan from end because we wanna get the next greater permutation. We wanna find the ascending order numbers because if we get that, we know that the next permutation will be after that number.  We also need to figure out the smallest number which is greater than the number we found, and swap them. At least, we shall sort the numbers after i in ascending order.