Find Next Permutation of Array Optimal Algorithm

Contents

ProblemExamplesVisualizationSolutionAlgorithmCodeTimeSpace

Problem Statement❯

Given an array of integers, your task is to rearrange the elements to form the next lexicographical permutation of the array.

  • If such a permutation exists, return the next greater permutation using the same digits.
  • If the array is already the highest possible permutation, return the lowest possible permutation (i.e., sorted in ascending order).

This must be done in-place, meaning you cannot use extra memory for another array.

Examples❯

Input Array Next Permutation Description
[1, 2, 3] [1, 3, 2] Normal case: 1-2-3 → 1-3-2 is the next permutationVisualization
[3, 2, 1] [1, 2, 3] Already the largest permutation, so return smallest (reverse sort)Visualization
[1, 1, 5] [1, 5, 1] Duplicates are handled: swap to get next valid permutationVisualization
[1] [1] Single element, no next permutation possibleVisualization
[] [] Empty array, return as-isVisualization
[1, 3, 2] [2, 1, 3] Mid permutation: find pivot and rearrangeVisualization
[2, 3, 1] [3, 1, 2] Pivot is at index 0, swap with just larger and reverse restVisualization

Visualization Player

Solution❯

The goal of this problem is to find the next permutation in dictionary (lexicographical) order. Think of all permutations of the array elements being sorted — your task is to move to the very next one in that sorted list.

Let’s discuss how this works and what outcomes we may expect, depending on the input.

🧩 Case 1: Normal Next Permutation Exists

Suppose the array is not in the highest possible order. We can still find a next greater permutation. To do that:

  • We look from right to left and find the first element that is smaller than its right neighbor. This element is our pivot.
  • Then we look again from the right and find the smallest element that is larger than the pivot — and we swap them.
  • Finally, we reverse the subarray after the pivot to get the smallest possible arrangement following the pivot.

This gives us the next greater permutation.

Case 2: Already the Last Permutation

If the array is in descending order (like [3, 2, 1]), it is already the last permutation. There's no greater permutation possible. In this case, the next permutation is just the smallest one — so we sort the array in ascending order.

🔄 Case 3: Duplicates Present

Even if the array has repeated numbers, the same logic applies. For example, in [1, 1, 5], the pivot is the first 1, and the next greater element is 5. We swap them and reverse the rest to get [1, 5, 1].

Case 4: Single Element or Empty Array

  • For a single element array, there is no rearrangement possible. So the array remains the same.
  • For an empty array, we return it as-is. There’s no permutation to perform.

Summary

This optimal solution works in linear time and does not use extra space. It’s based on the observation that the next permutation is formed by modifying the suffix of the array in a smart way. By finding a pivot, swapping, and reversing a part of the array, we efficiently jump to the next valid permutation.

Algorithm Steps❯

  1. Given an array arr of integers.
  2. Start from the end and find the first index i where arr[i] < arr[i+1]. This identifies the pivot.
  3. If no such index exists, reverse the entire array to get the lowest permutation.
  4. Otherwise, find the next larger element than arr[i] from the end of the array, say index j, and swap arr[i] and arr[j].
  5. Finally, reverse the subarray from i+1 to the end to get the next permutation.

Code

Python
JavaScript
Java
C++
C
def next_permutation(arr):
    n = len(arr)
    i = n - 2
    while i >= 0 and arr[i] >= arr[i + 1]:
        i -= 1
    if i >= 0:
        j = n - 1
        while arr[j] <= arr[i]:
            j -= 1
        arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1:] = reversed(arr[i + 1:])
    return arr

# Sample Input
arr = [1, 2, 3]
print("Next Permutation:", next_permutation(arr))

Time Complexity

CaseTime ComplexityExplanation
Best CaseO(n)In the best case, we still need to scan from the end to find the pivot, and possibly reverse a subarray — all in linear time.
Average CaseO(n)On average, the algorithm scans the array from the end to find the pivot and the next greater element, followed by a reversal — all linear operations.
Worst CaseO(n)In the worst case, such as when the array is in descending order, we have to reverse the entire array — still a linear time operation.

Space Complexity

O(1)

Explanation: The algorithm modifies the array in-place without using any extra space except a few variables for indices and swapping.