Find Next Permutation of Array - Visualization

Arrays

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

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

Solution❯

Understanding the Problem

We are given an array of integers that represents a permutation of numbers. Our goal is to find the next permutation in lexicographical (dictionary) order. If such a permutation is not possible (i.e., the given permutation is the highest possible), we return the lowest permutation by sorting the array.

Think of listing all permutations in sorted order — we want to return the one that comes immediately after the current array.

Step-by-Step Plan with Example

Let's take the example [1, 2, 3]. Here's how we solve it:

Step 1: Find the Pivot

Scan the array from right to left and find the first number that is smaller than its next number. This is our pivot. In our example, 2 is the pivot (since 2 < 3).

Step 2: Find the Successor

Now, from the right side again, find the first number that is greater than the pivot. In our case, 3 is greater than 2.

Step 3: Swap the Pivot and Successor

Swap 2 and 3. Now the array becomes [1, 3, 2].

Step 4: Reverse the Suffix

Finally, reverse the part of the array that comes after the pivot's original index. But here, it's already just a single element (2), so no actual change is needed.

The final result is [1, 3, 2] — the next permutation!

Edge Case 1: Last Permutation Already

If the array is in descending order, like [3, 2, 1], then it is the highest possible permutation. There is no "next" permutation.

In this case, we simply reverse the array to get the lowest permutation: [1, 2, 3].

Edge Case 2: Duplicates Present

The same logic works even if the array contains duplicates. For example, take [1, 1, 5]:

  • Find pivot → first 1
  • Find successor → 5
  • Swap → [1, 5, 1]
  • Reverse the suffix → remains [1]

Final result: [1, 5, 1]

Edge Case 3: One or Zero Elements

  • If the array has only one element, e.g., [7], no rearrangement is possible. We return the same array.
  • If the array is empty, we return it as-is.

Summary

This approach works efficiently in O(n) time with no extra space. The key idea is:

  1. Find a pivot (first dip from right)
  2. Find the next greater element to pivot (successor)
  3. Swap them
  4. Reverse the suffix

This gives us the next permutation in place without generating all possible permutations.

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

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>

void reverse(int arr[], int start, int end) {
    while (start < end) {
        int temp = arr[start];
        arr[start++] = arr[end];
        arr[end--] = temp;
    }
}

void nextPermutation(int arr[], int n) {
    int i = n - 2;
    while (i >= 0 && arr[i] >= arr[i + 1]) i--;
    if (i >= 0) {
        int j = n - 1;
        while (arr[j] <= arr[i]) j--;
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    reverse(arr, i + 1, n - 1);
}

int main() {
    int arr[] = {1, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    nextPermutation(arr, n);
    printf("Next Permutation: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    return 0;
}

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.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...