Data Structures & Algorithms (Arrays & Strings): Next Permutation

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

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).

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [3,2,1]
Output: [1,2,3]
Explanation: Rearranged [3,2,1] in the lowest possible order since it does not have a lexicographical larger rearrangement.

Playground: Leetcode 31

Key Observation

We need to find the rightmost index (often called pivot) where a larger element exists on the right.

The element at the pivot index can be swapped with a larger element on its right to get a bigger permutation, but to get the next permutation, it must be swapped with the smallest element greater than it on the right.

Before the swap, the suffix (right part of the array) is in descending order, meaning it represents the largest possible arrangement of those elements. After swapping the pivot with the next greater element, the suffix remains largely in descending order, which is still too large for our goal.

Since we want the next smallest greater permutation, we must minimize this suffix. Reversing it converts the descending order into ascending order, giving the smallest possible arrangement and ensuring the overall permutation is just slightly larger than the original.

Greedy Approach

Find the rightmost dip, swap with the next greater element, and reverse the suffix.

Visualization

Algorithms

public static void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

public static void reverse(int[] nums, int start, int end) {
    while(start < end) {
        swap(nums, start, end);
        start++;
        end--;
    }
}

public void nextPermutation(int[] nums) {

    // Step 1: Find the pivot index
    int pivotIndex = -1;
    for(int i = nums.length - 2; i >= 0; i--) {
       if(nums[i] < nums[i+1]) {
            pivotIndex = i;
            break;
       }
    }

    // If no pivot, reverse whole array (last permutation → first)
    if(pivotIndex == -1) {
        reverse(nums, 0, nums.length);
        return;
    }

    // Step 2: Swap the pivot element with the next greater element
    for(int j = nums.length - 1; j > pivotIndex; j--) {
        if(nums[j] > nums[pivotIndex]) {
            swap(nums, pivotIndex, j);
            break;
        }
    }

    // Step 3: Reverse the suffix to the right of pivot
    reverse(nums, pivotIndex + 1, nums.length - 1);
    
}

Time Complexity

In the worst case, when the array is in descending order, we scan the array once to check for a pivot (and find none), and then perform another full pass to reverse the entire array. Hence, overall time complexity = O(2*n) ~ O(n).

Space Complexity

We are not using any extra dynamic data structures. Since, all operations are performed in-place, the overall space complexity = O(1).