31. Next Permutation - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Description:
Given an array of integers, rearrange the numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible (i.e. the array is in its highest possible order), 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.

Examples:

Example 1:
- Input: [1, 2, 3]
- Output: [1, 3, 2]
- Explanation: The next permutation of the sequence [1, 2, 3] is [1, 3, 2].
Example 2:
- Input: [3, 2, 1]
- Output: [1, 2, 3]
- Explanation: Since [3, 2, 1] is the highest permutation, the next permutation is the lowest one, which is [1, 2, 3].
Example 3:
- Input: [1, 1, 5]
- Output: [1, 5, 1]
- Explanation: The next permutation is achieved by swapping the last two elements.

Constraints:

The number of elements in the array is in the range [1, 100].
Each element is within the range [0, 100].

Hints Before the Solution

Identify the "Pivot":
Look from right to left to find the first index where the current number is less than the number immediately after it. This position is called the pivot.
Find the Right Element to Swap:
Once you have found the pivot, search to the right of it to find the smallest number that is larger than the pivot element. Swap these two.
Reverse the Suffix:
After swapping, reverse the subarray (or suffix) that comes after the pivot’s original position. This will transform that part into its lowest possible order, giving you the next permutation.

1. Brute Force Approach

Idea

Generate All Permutations:
Generate all possible permutations of the array, sort them lexicographically, and then find the permutation that comes immediately after the current one.

Drawbacks

Time Complexity: Generating all permutations requires O(n!) time, which is impractical even for moderate-sized arrays.
Space Complexity: Storing all permutations uses extra space.

When to Use

Mainly for understanding the concept; however, it is not feasible for real coding interviews due to its inefficiency.

2. Optimal Approach (In-Place, O(n) Time)

Key Steps

Find the Pivot:
Start from the end of the array and move left to find the first element that is smaller than its next element. This element is the pivot.
Find the Rightmost Successor:
In the suffix (the part of the array to the right of the pivot), find the element that is just larger than the pivot.
Swap the Pivot and the Successor:
Swap these two elements.
Reverse the Suffix:
Reverse the order of the elements in the suffix. This ensures the suffix is in ascending order (i.e., the smallest order).

Why It Works

The algorithm works by finding the smallest change needed to get a permutation that is just one step greater than the current one. If no pivot is found, the entire array is reversed (which is the smallest permutation).

Python Code

Python3

. . . .

Java Code

Java

. . . .

Complexity Analysis

Time Complexity:
- Optimal Approach: O(n)
  - Finding the pivot requires a single pass from the right (O(n)).
  - Swapping and then reversing the suffix is also O(n) in the worst case.
Space Complexity:
- O(1) extra space since the modifications are done in-place.

Step-by-Step Walkthrough with Visual Example

Let’s walk through the optimal approach with the example: [1, 3, 5, 4, 2].

Find the Pivot:
- Start from index 3 (value 4) and move left.
- Compare: 5 (index 2) and 4 (index 3) → 5 ≥ 4 so move left.
- Compare: 3 (index 1) and 5 (index 2) → 3 < 5.
  Pivot found at index 1 (value 3).
Find the Successor:
- Look to the right of the pivot (subarray: [5, 4, 2]).
- From the right, the first element greater than 3 is 4 (at index 3).
Swap the Pivot and the Successor:
- Swap 3 and 4:
  Array becomes: [1, 4, 5, 3, 2].
Reverse the Suffix:
- Reverse the subarray after index 1 (i.e., reverse [5, 3, 2]).
- Reversed suffix: [2, 3, 5].
- Final array: [1, 4, 2, 3, 5].

Common Mistakes & Edge Cases

Common Mistakes

Missing the Pivot:
Not scanning from the right or stopping too early can cause you to miss the correct pivot.
Incorrect Suffix Reversal:
Failing to reverse the suffix completely might leave the permutation in a non-lexicographically minimal order.
Off-by-One Errors:
Improper index handling during the scan or reversal can lead to incorrect results.

Edge Cases

Descending Array:
If the input is already the highest permutation (e.g., [3, 2, 1]), the algorithm correctly reverses the whole array.
Single Element:
Arrays with one element should remain unchanged.
Arrays with Duplicate Elements:
Ensure that your comparisons handle duplicate values correctly (e.g., [1, 1, 5]).

Alternative Variations

Previous Permutation:
Find the lexicographically previous permutation.
Permutation Sequence:
Determine the kth permutation sequence of n numbers.

Permutation Sequence (LeetCode):
Given n and k, return the kth permutation sequence.
Next Greater Element:
Find the next greater element for every element in an array.
Longest Increasing Subsequence:
Find the longest increasing subsequence in an array.
Subsets and Combinations Problems:
Problems that involve generating or manipulating permutations, subsets, or combinations.