How do you solve Next Permutation on LeetCode?

Next Permutation (LeetCode #31) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: The key observation is that the next permutation can be found by identifying the rightmost ascent in the array, which indicates where the next permutation can be formed.

What is the brute force solution for Next Permutation?

The brute force approach for Next Permutation is Brute Force, with O(n²) time complexity and O(n!) space complexity. The brute force approach involves generating all possible permutations of the array and then finding the next permutation in lexicographical order. This is straightforward but inefficient due to the factorial growth of permutations. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Next Permutation?

Next Permutation uses the following concepts: Array, Two Pointers. The recommended patterns to study are: Array, Two Pointers.

What are the interview tips for Next Permutation?

When you first see this problem, clarify the constraints and ensure you understand what is meant by 'next permutation'. Communicate your thought process clearly, explaining how you would find the pivot and the successor. Mention edge cases like arrays that are already in descending order or arrays with duplicate elements.

What are common mistakes when solving Next Permutation?

Students often forget to handle the case where the array is in descending order, leading to incorrect outputs. Another common mistake is not reversing the suffix after swapping, which results in an incorrect permutation.

#31

Next Permutation

Medium

ArrayTwo PointersArrayTwo Pointers

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(n!)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal approach leverages the properties of permutations to find the next permutation in-place without generating all permutations. It identifies the rightmost ascent in the array and swaps elements to form the next permutation efficiently.

⚙️

Algorithm

4 steps

1Step 1: Traverse the array from right to left and find the first pair where nums[i] < nums[i + 1]. This identifies the pivot point.
2Step 2: If no such pair exists, reverse the entire array to get the smallest permutation.
3Step 3: If a pivot is found, traverse from the end to find the first element larger than the pivot, then swap them.
4Step 4: Reverse the sub-array to the right of the pivot to get the next permutation.

solution.py17 lines

1# Full working Python code with comments
2def next_permutation(nums):
3    n = len(nums)
4    # Step 1: Find the pivot
5    i = n - 2
6    while i >= 0 and nums[i] >= nums[i + 1]:
7        i -= 1
8    if i >= 0:
9        # Step 3: Find the rightmost successor
10        j = n - 1
11        while nums[j] <= nums[i]:
12            j -= 1
13        # Swap
14        nums[i], nums[j] = nums[j], nums[i]
15    # Step 4: Reverse the suffix
16    nums[i + 1:] = reversed(nums[i + 1:])
17

ℹ

Complexity note: The optimal approach runs in linear time O(n) because we only traverse the array a few times (finding the pivot, finding the successor, and reversing the suffix). The space complexity is O(1) since we are modifying the array in place.

1The key observation is that the next permutation can be found by identifying the rightmost ascent in the array, which indicates where the next permutation can be formed.
2Another important insight is that reversing the suffix of the array after the pivot ensures that we get the smallest possible arrangement of that suffix, leading to the next permutation.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.