Next Permutation

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 all the permutations of arr: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1].

The next permutation of an array of integers is the next lexicographically greater permutation of its integers. More formally, if all the permutations of the array are sorted in lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted order.

If such arrangement is not possible (i.e., the array is the last permutation), then rearrange it to the lowest possible order (i.e., sorted in ascending order).

Brute Force#

Generate every permutation of the array recursively using backtracking, sort all permutations lexicographically, then locate the current permutation and return the one at the next index (wrapping to the first if we are already at the last). This is correct but catastrophically expensive: there are n! permutations, sorting them costs O(n! log n!), and storing them requires O(n!) space — completely impractical for n <= 12 or more.

Why upper_bound instead of a linear search?

A linear scan for allPermutations[i] == nums finds the first occurrence of nums in the sorted list. When the input has duplicate elements (e.g. [1, 1, 2]), multiple identical permutations are generated. The first occurrence at index i means allPermutations[i+1] is the same permutation again — not the next distinct one.

upper_bound bypasses this: it finds the first permutation strictly greater than nums, so duplicates are automatically skipped.

sorted permutations of [1,1,2]:
  [1,1,2]  [1,1,2]  [1,2,1]  [1,2,1]  [2,1,1]  [2,1,1]
              ↑                                         ↑
     linear find lands here          upper_bound lands here (correct)
     → returns [1,1,2] again         → returns [1,2,1] ✓

class Solution {
public:
    void generateAllPermutations(vector<int>& nums, vector<vector<int>>& allPermutations, int idx) {
        if (idx == nums.size() - 1) {
            allPermutations.push_back(nums);
            return;
        }
        for (int i = idx; i < nums.size(); i++) {
            swap(nums[idx], nums[i]);
            generateAllPermutations(nums, allPermutations, idx + 1);
            swap(nums[idx], nums[i]);
        }
    }

    void nextPermutation(vector<int>& nums) {
        vector<vector<int>> allPermutations;
        generateAllPermutations(nums, allPermutations, 0);

        int n = allPermutations.size();
        sort(allPermutations.begin(), allPermutations.end());

        // upper_bound gives the first permutation strictly greater than nums,
        // correctly skipping duplicates that a linear search would stumble on.
        auto it = upper_bound(allPermutations.begin(), allPermutations.end(), nums);
        if (it == allPermutations.end())
            nums = allPermutations[0];   // wrap around to smallest
        else
            nums = *it;
    }
};

Time Complexity: O(n! · n log n) — n! permutations, each of length n, sorted

Space Complexity: O(n!)

Optimal Approach#

Intuition#

• Find the Pivot (First decreasing point from right)
  • We scan from right to left to find where order breaks
  • We look for: nums[i] < nums[i+1]
  • Why? Because everything to the right of that point is already in descending order — meaning it is the largest possible arrangement of that suffix.
• If no pivot found → already largest permutation
  • So next permutation = smallest permutation: sort the array
• Find the next greater element than pivot
  • we want the smallest number greater than pivot on the right side.
  • swap the found number with the pivot.
• Fix the right side (make it smallest possible)
  • To get the next permutation, we need the smallest suffix.
  • sort the right side.

class Solution {
   public:
    void nextPermutation(vector<int>& nums) {
        
        int pivot = -1;

        //find pivot
        for(int i=nums.size()-2;i>=0;i--){
            if(nums[i]<nums[i+1])
            {
                pivot = i;
                break;
            }
        }

        //if no pivot found - last permutation
        if(pivot == -1){
            reverse(nums.begin(), nums.end());
            return;
        }

        // find swap for pivot
        for(int i=nums.size()-1;i>=pivot;i--){
            if(nums[i]>nums[pivot]){
                swap(nums[i], nums[pivot]);
                break;
            }
        }

        //sort the array to the right of pivot
        reverse(nums.begin() + pivot+1, nums.end());
    }
};

Time Complexity: O(n)

• O(n) to find pivot
• O(n) to find swap
• O(n log n) sort (can be O(n) if reverse used)

Space Complexity: O(1)

Follow Up#

What if the input contained many duplicate elements? Would your current logic for finding the swap element still be the most efficient approach?#

The current scan for the swap element walks from the right end toward the pivot:

for (int i = nums.size()-1; i >= pivot; i--) {
    if (nums[i] > nums[pivot]) { swap(...); break; }
}

This is O(n) in the worst case. With many duplicates, large stretches of equal values are skipped one by one.

Key insight: the suffix to the right of the pivot is always in descending order (that is why the pivot was chosen — it is the first place where the order breaks). A descending range is a reversed sorted range, so lower_bound with a reverse comparator finds the target in O(log n) instead of O(n).

We want the rightmost element strictly greater than nums[pivot] (rightmost so that with duplicates we pick the smallest valid swap). In the descending suffix that is the last element satisfying > pivot, which lower_bound on the reversed range gives directly:

// suffix [pivot+1 .. n-1] is descending
auto suffix_begin = nums.rbegin();                        // points at nums[n-1]
auto suffix_end   = nums.rend() - (pivot + 1);           // points just before pivot

// lower_bound on reversed range (descending order) finds first element <= nums[pivot]
// The element just before it is the rightmost element > nums[pivot]
auto it = lower_bound(suffix_begin, suffix_end, nums[pivot],
                      [](int a, int b){ return a > b; }); // descending comparator

swap(*it, nums[pivot]);
reverse(nums.begin() + pivot + 1, nums.end());

Complexity comparison:

The asymptotic class stays O(n) because the pivot search dominates, but the constant factor on the swap step drops significantly when the duplicate-heavy suffix is long — for example a 10 000-element suffix with all equal values reduces from 10 000 comparisons to ~14.