Coding Interview: Next Permutation

Permutation (and combination) problems are highly recurrent in code interviews and can be challenging due to the fundamentals needed to address the problem efficiently.

In this blog post, we will see some approaches and techniques to address the next permutation problem, starting from the approach based on brute force to address more efficient solutions.

Let's get started!

Problem statement

Let's take a look at the problem definition:

"The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container." [1]

For example:

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

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

Case 3Input: nums = [2,0,2,2]Output: [2,2,0,2]

In a nutshell, the problem requires the following permutation given an ascending order from the given permutation as input. If there is no larger permutation, return the permutation with the smallest lexicographical value. In figure 2 we see a representation of the permutations generated from [1,2,3] ordered lexicographically.

Once the definition and scope of the problem is clear, let's proceed with the solutions, starting with a brute force-based approach and then applying a technique to obtain a more efficient solution. Let's go for it!

Approach 1: Brute force

The key idea for the brute-force approach is to generate all the permutations, sort them lexicographically, and extract the next permutation determined by input . In code snippet 1 we can see the implementation of the brute force approach.

The number of permutations given a set of n elements is n! , so the runtime complexity is O(N!) and O(N) for memory usage. It is important to mention that in the brute force-based approach presented in code snippet 1, the dominant runtime complexity is O(N!). Although implementing a Min-Heap has complexity O(N Log N) and finding the next permutation has complexity O(N), the resulting dominating complexity is O(N!).

An important topic derived from this problem and that can be very useful for a code interview, is the generation of permutations using specific recursion techniques such as backtracking and to which I will dedicate an entire blog. In the meantime, you can take a look at code snippet 1 on line 10 where the función backtrack() is defined for permutation generation in a efficient and elegant way.

Continuing with the problem, how can we find the next permutation without generating all the permutations? Well, let's see in detail in the next section.

Approach 2: The trick

The next permutation problem, at first sight, seems to have a high degree of complexity. However, it is simpler than it seems. In fact, in the simplest form, the problem can be solved in a single pass. The "trick" is knowing, inferring, or figuring out the steps to solve it this way.

The steps are described as follows:

1. Iterate over array nums from back to front until finding the first non-increasing element in the sequence, say nums[i-1] .

2. If the index i-1 is not zero, the first element greater than element nums[i-1] is found and swapped. If the index i-1 is zero, it means that the sequence is ordered in descending order and therefore it is the largest sequence that can be formed, consequently, the process ends by returning the reversed sequence.

3. Elements starting from index i are reversed.

In figure 3 we can see a visual representation of two cases when addressing the next permutation problem.

In code snippet 2 we can see the definition of the function to solve the next permutation problem efficiently.

Since the nums array is traversed at most twice, the runtime complexity is linear O(N) and memory usage remains constant O(1) because no extra memory is required to solve the problem.

Great, now you have an alternative to address the next permutation problem if you come across it in a code interview.

Conclusion

Permutation and combination problems require specific techniques to be able to solve them efficiently (e.g. backtracking). However, this particular problem can be solved in this alternative way. It becomes controversial to solve this problem because it can be seen as "knowing the trick or not", which is understandable but it is not a decision that we (those who solve these types of problems in interviews), can have under. control.

References

[1] https://leetcode.com/problems/next-permutation/