Leetcode 31: Next Permutation

 

1. Problem Statement (Simple Explanation):

You’re given an array of integers nums representing a permutation.

You must rearrange nums in-place to form the next lexicographically greater permutation.

• If such a permutation exists: transform nums into it.

• If not (i.e., nums is the highest permutation), rearrange nums into the lowest possible order (sorted ascending).

Constraints:

• In-place (only constant extra memory).

• 1 <= nums.length <= 100

• 0 <= nums[i] <= 100

2. Examples:

Example 1:

Input: nums = [1,2,3]

Permutations in order:

[1,2,3]

[1,3,2]  <-- next

[2,1,3]

[2,3,1]

[3,1,2]

[3,2,1]

Output: [1,3,2]

Example 2:

Input: nums = [3,2,1]

This is the largest permutation. The next permutation wraps to the smallest:

Output: [1,2,3]

Example 3:

Input: nums = [1,1,5]

Next permutations:

[1,1,5]

[1,5,1]  <-- next

[5,1,1]

Output: [1,5,1]

3. Intuition – Classic Next Permutation Algorithm:

We want the next lexicographically larger arrangement. Think of the array as a number; we want the smallest number larger than the current using the same digits.

Algorithm idea (standard):

1. Scan from right to left to find the first index i where:

nums[i] < nums[i+1]

This is the pivot where the descending order breaks.

1. If no such i exists (array is fully non-increasing from left to right, like [3,2,1]), then this is the last permutation.

2. So we just reverse the entire array to get the first permutation (ascending).

2. If such i is found:

• Find the smallest element greater than nums[i] on the right side (i.e., in nums[i+1 .. end]).

• Because the right side is non-increasing, we can find this by scanning from the right until we find the first nums[j] > nums[i].

3. Swap nums[i] and nums[j].

4. Reverse the subarray nums[i+1 .. end]:

• This makes the suffix the lowest possible order (ascending) after the pivot so that the whole array is the next lexicographically smallest arrangement.

4. Pseudo code:

Complexity:

For all implementations:

• Time: O(n) – we scan from the right, then potentially scan again and reverse a suffix.

• Space: O(1) extra – in-place operations only.

Example Walkthrough – [1,2,3]:

• From right:

• i = 1: nums[1]=2 < nums[2]=3 → pivot at i = 1.

• Find j from right such that nums[j] > nums[1]:

• j = 2, nums[2]=3 > 2.

• Swap → [1,3,2].

• Reverse suffix i+1..end → i+1 = 2 → only [2] → stays [1,3,2].

Example Walkthrough – [3,2,1]:

• From right:

• i = 1: 2 >= 1 → continue.

• i = 0: 3 >= 2 → continue.

• i = -1 → no pivot (array is descending).

• Since i < 0, reverse entire array:

• [1,2,3].

5. Java code:

6. C code:

7. C++ code:

8. Python code:

9. JavaScript code: