Leetcode: Next Permutation

This is part of a series of Leetcode and other curated solution explanations (index).
If you liked this solution or found it useful, please like this post.

Leetcode Problem #31 (Medium): Next Permutation

31. Next Permuation

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

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

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

Example 1:

Input: nums = [1,2,3]
Output: [1,3,2]

Example 2:

Input: nums = [3,2,1]
Output: [1,2,3]

Example 3:

Input: nums = [1,1,5]
Output: [1,5,1]

Example 4:

Input: nums = [1]
Output: [1]

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 100

Solution

The idea is little tricky, first of all the answer is not a number, but a rearrangement of digits shown in the input array. This might gives us a hint that we don't have to calculate the number by index 10.

or

You might think of that solution as brute force:

• create all permutations of the input,
• generate the number from that input variant,
• find the next largest at this point you might be think of storing the array as a HashMap index and the number as its value

And there's nothing wrong in this except for the runtime O (n x n!) - WHAT!

So, immediately we have to pivot to some other approach - do we really need to calculate ALL permutations!

Let's see from an example:

input = [1, 2, 3]
solution = [1, 3, 2]

can we say that we simply swapper the larger digit with the immediate smaller one from the right?

ok, but this will not work everytime

input = [1, 3, 2]
solution = [2, 1, 3]

the ONLY trick needed here:
we start from right - compare the two digits until we find the index which is just smaller than 2, i.e. we compare n-1 <= n until we reach the leftmost or the failing case.

for [1, 3, 2] we reached till i = 0 (1)

now if we had reached -1 -> we cannot produce a bigger number, thanks to the problem statement, we simply reverse the number and return.

but if i >=0 , we again start from the end (say j), until we find a number greater than i
2 <= 1
so, j = 2 (2)

we swap i j
[2, 3, 1]

and the final step
we reverse all digits after the ith index (i+1)
2 [3, 1] -> 2 [1, 3]

Implementation:

    public static void nextPermutation(int[] nums) {
        int i = nums.length - 2;

        while (i >= 0 && nums[i + 1] <= nums[i]) {
            i--;
        }

        if (i >= 0) {
            while (nums[j] <= nums[i]) {
                j--;
            }

            swap(nums, i, j);
        }

        reverse(nums, i + 1);
    }

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

    private static void reverse(int[] nums, int start) {
        int i = start, j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }

**Bonus
since some of you like python -> Enjoy ;)

def next_perm(n):
    i = len(n) - 2
    while i >= 0 and n[i + 1] <= n[i]:
        i -= 1

    if i >= 0:
        j = len(n) - 1
        while n[j] <= n[i]:
            j -= 1

        swap(n, i, j)

    return reverse(n, i + 1)


def swap(n, i, j):
    n[i], n[j] = n[j], n[i]


def reverse(n, from_index):
    res = []
    for i in range(0, from_index):
        res.append(n[i])

    for i in range(len(n) - 1, from_index - 1, -1):
        res.append(n[i])

    return res