Next Permutation

Problem

Given a number N. Find the smallest number greater than N such that the digits are a permutation of the number N.

You can assume number N represented as array.

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

For example, for arr = [1,2,3], the following are considered permutations of arr: [1,2,3], [1,3,2], [3,1,2], [2,3,1].

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. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

For example, the next permutation of arr = [1,2,3] is [1,3,2].
Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.

Given an array of integers nums, find the next permutation of nums.

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

Example

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]

Solution

Method 1 - Brute Force

This is the naive approach:

Generate and store all possible permutations of the elements.
Identify the input within these permutations.
Output the permutation that follows it.

We have solved this problem - Permutations of Array 1. But the time complexity is O(n*n!), and space complexity is also O(n!).

Method 2 - Using Partition

Lets take [1,2,3] as example. These are the permutations ranks: [1,2,3] , [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]

Intuitions

Intuition 1

Find the largest index i such that nums[i] < nums[i + 1]. If no such index exists, the array is the last permutation; otherwise, we proceed to the next step.

Now, if we look closely, for eg. from [1,2,3] to [1,3,2], the change happens from right, for eg. we move 3 forward. Likewise, when we move from [2,1,3] -> [2,3,1] we replace next min element from right by just larger number, to permute.

// find first value smaller than right neighbour
int partitionIdx = -1;
for (int i = n - 2; i > 0; i--) {
	if (nums[i] < nums[i + 1]) {
		partitionIdx = i;
		break;
	}
}

Intuition 2

If the partitionIdx is -1, that means array is already sorted in descending order, and it is the last permutation by rank. So, we just reverse the array to get the array in the increasing order. For eg. for [3,2,1], we have partitionIdx = -1 i.e. hence we reverse the array and get [1, 2, 3].

if(partitionIdx == -1) {
	reverse(nums, 0, n-1);
	return;
}

Intuition 3

Find the largest or rightmost index j greater than i such that nums[i] < nums[j] and swap the values of nums[i] and nums[j].

Once this case is out (i.e. array is not in descending order, and partitionIdx is not -1), we have to find the smallest value after the partitionIdx,then swap with it. And after the pivot, the rest of the array will be kind of in decreasing order. And we want to find the smallest value larger than the pivot element and swap with it, and as array is in decreasing order, we will find it at the rightmost index point after the pivot. Lets call it swapIdx.

For eg. for [1, 2, 3], and the rightmost index after 1 where nums[partitionIdx] < nums[j] is 2. So, we swap 2 and 3, and our array becomes [1, 3, 2]

To find this swapIdx, we can either use linear search or binary search. Binary search can be used as array to the right is already sorted in decreasing as we checked with the index earlier. Once swap is done, we reverse from partitionIdx+1 to n-1.

Intuition 4

Reverse subarray nums[i + 1:] to get the smallest lexicographical order from that part.

Consider the array [1, 2, 5, 4, 3, 0]. We have pivot at value 2, with index 1. We swap it with element 3 at index 5, as it is the rightmost element greater than 2.

Now, the array becomes [1, 3, 5, 4, 2, 0]. As you can see it is not the next largest palindrome, as even though we moved 3 forwards, larger number like 5, 4 are at more significant positions. So, we should correct it by sorting or reversing the array from nums[i+1:]. We dont need to sort, as the subarray nums[i+1:] is already in descending order, so reversing is sufficient.

So, our correct answer becomes: [1, 3, 0, 2, 4, 5].

Algorithm

Identify Pivot - Find the largest index i or pivot such that nums[i] < nums[i + 1]. If no such index exists, the array is the last permutation; otherwise, we proceed to the next step. (Subarray right of pivot will be non-increasing suffix)
Identify swap point - Find the largest index j greater than i such that nums[i] < nums[j].
**Swap the values of nums[i] and nums[j].
Reverse the sub-array nums[i + 1:] to get the smallest lexicographical order from that part

Dry Run

Input

$$ \begin{array}{|c|c|c|c|c|c|} \hline 1 & 2 & 5 & 4 & 3 & 0 \\ \hline \end{array} $$

Step 1 - Identify Pivot

We identify pivot(in orange), i.e. largest index i such that nums[i] < nums[i+1]. Elements right of pivot is non-increasing suffix (in light blue). $$ \begin{array}{|c|c|c|c|c|c|} \hline 1 & \colorbox{Dandelion}2 & \colorbox{SkyBlue}5 & \colorbox{SkyBlue}4 & \colorbox{SkyBlue}3 & \colorbox{SkyBlue}0 \\ \hline \end{array} $$

Step 2 - Identify swap point

Now, we find the swap point i.e. largest index j such that nums[i] < nums[j], and here it is number 3 (in green). $$ \begin{array}{|c|c|c|c|c|c|} \hline 1 & \colorbox{Dandelion}2 & \colorbox{SkyBlue}5 & \colorbox{SkyBlue}4 & \colorbox{YellowGreen}3 & \colorbox{SkyBlue}0 \\ \hline \end{array} $$

Step 3 - Swap Pivot and Swap Point

$$ \begin{array}{|c|c|c|c|c|c|} \hline 1 & \colorbox{YellowGreen}3 & \colorbox{SkyBlue}5 & \colorbox{SkyBlue}4 & \colorbox{Dandelion}2 & \colorbox{SkyBlue}0 \\ \hline \end{array} $$

Step 4 - Reverse or Sort the suffix

$$ \begin{array}{|c|c|c|c|c|c|} \hline 1 & \colorbox{YellowGreen}3 & \colorbox{LightBlue}0 & \colorbox{LightBlue}2 & \colorbox{LightBlue}4 & \colorbox{LightBlue}5 \\ \hline \end{array} $$

Code

Java

Linear Search

class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int i = n - 2;
        
        // Step 1: Find the largest index `i` such that `nums[i] < nums[i + 1]`
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        
        if (i >= 0) {
            // Step 2: Find the largest index `j` greater than `i` such that `nums[i] < nums[j]`
            int j = n - 1;
            while (j >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            
            // Step 3: Swap the values of `nums[i]` and `nums[j]`
            swap(nums, i, j);
        }
        
        // Step 4: Reverse the sub-array `nums[i + 1:]`
        reverse(nums, i + 1, n - 1);
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            swap(nums, start, end);
            start++;
            end--;
        }
    }
}

Binary Search

public void nextPermutation(int[] nums) {
    if (nums == null || nums.length <= 1) return;
	int n = nums.length;
	
	// find first value smaller than right neighbour
	int index = n-2;
	for (int i = n - 2; i >= 0; i--) {
		if (nums[i] < nums[i+1]) {
			index = i;
			break;
		}
	}

	if(index == -1) {
		reverse(nums, 0, n-1);
		return;
	}
	
    //find the smallest value after partition index,then swap with it
	int current = nums[index];
	int start = index+1;
	int end = n-1;
	int swapIdx = -1;
	//BinarySearch since array to the right is already sorted to find the first occurance of next Greatest element from our current Element
	while(start<=end) {
		int mid = start + (end-start)/2;
		if(nums[mid]>current) {
			swapIdx = mid;
			start = mid+1;
		}
		else{
			end = mid-1;
		}
	}
	swap(nums,index,swapIdx);
	reverse(nums,index+1,nums.length-1);
}

Python

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        n = len(nums)
        i = n - 2
        
        # Step 1: Find the largest index `i` such that `nums[i] < nums[i + 1]`
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1
        
        if i >= 0:
            # Step 2: Find the largest index `j` greater than `i` such that `nums[i] < nums[j]`
            j = n - 1
            while j >= 0 and nums[i] >= nums[j]:
                j -= 1
            
            # Step 3: Swap the values of `nums[i]` and `nums[j]`
            nums[i], nums[j] = nums[j], nums[i]
        
        # Step 4: Reverse the sub-array `nums[i + 1:]`
        self.reverse(nums, i + 1, n - 1)
    
    def reverse(self, nums: List[int], start: int, end: int) -> None:
        while start < end:
            nums[start], nums[end] = nums[end], nums[start]
            start += 1
            end -= 1

Complexity

⏰ Time complexity: O(n)
🧺 Space complexity: O(1)

Problem#

Example#

Solution#

Method 1 - Brute Force#

Method 2 - Using Partition#

Intuitions#

Intuition 1#

Intuition 2#

Intuition 3#

Intuition 4#

Algorithm#

Dry Run#

Input#

Step 1 - Identify Pivot#

Step 2 - Identify swap point#

Step 3 - Swap Pivot and Swap Point#

Step 4 - Reverse or Sort the suffix#

Code#

Java#

Linear Search#

Binary Search#

Python#

Complexity#