Next Permutation of Array

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.

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.

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.

#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;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void nextPermutation(vector<int>& arr) {
    int i = arr.size() - 2;
    while (i >= 0 && arr[i] >= arr[i + 1]) i--;
    if (i >= 0) {
        int j = arr.size() - 1;
        while (arr[j] <= arr[i]) j--;
        swap(arr[i], arr[j]);
    }
    reverse(arr.begin() + i + 1, arr.end());
}

int main() {
    vector<int> arr = {1, 2, 3};
    nextPermutation(arr);
    cout << "Next Permutation: ";
    for (int num : arr) cout << num << " ";
    return 0;
}

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

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

import java.util.*;
public class NextPermutation {
    public static void nextPermutation(int[] arr) {
        int i = arr.length - 2;
        while (i >= 0 && arr[i] >= arr[i + 1]) i--;
        if (i >= 0) {
            int j = arr.length - 1;
            while (arr[j] <= arr[i]) j--;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        reverse(arr, i + 1, arr.length - 1);
    }

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

    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        nextPermutation(arr);
        System.out.print("Next Permutation: ");
        for (int num : arr) System.out.print(num + " ");
    }
}

function nextPermutation(arr) {
    let i = arr.length - 2;
    while (i >= 0 && arr[i] >= arr[i + 1]) i--;
    if (i >= 0) {
        let j = arr.length - 1;
        while (arr[j] <= arr[i]) j--;
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }
    let left = i + 1, right = arr.length - 1;
    while (left < right) {
        [arr[left], arr[right]] = [arr[right], arr[left]];
        left++;
        right--;
    }
    return arr;
}

const arr = [1, 2, 3];
console.log("Next Permutation:", nextPermutation(arr));

package main
import (
    "fmt"
)

func reverse(arr []int, start int) {
    end := len(arr) - 1
    for start < end {
        arr[start], arr[end] = arr[end], arr[start]
        start++
        end--
    }
}

func nextPermutation(arr []int) {
    i := len(arr) - 2
    for i >= 0 && arr[i] >= arr[i+1] {
        i--
    }
    if i >= 0 {
        j := len(arr) - 1
        for arr[j] <= arr[i] {
            j--
        }
        arr[i], arr[j] = arr[j], arr[i]
    }
    reverse(arr, i+1)
}

func main() {
    arr := []int{1, 2, 3}
    nextPermutation(arr)
    fmt.Print("Next Permutation: ")
    for _, val := range arr {
        fmt.Printf("%d ", val)
    }
}

fn next_permutation(arr: &mut Vec<i32>) {
    let n = arr.len();
    if n < 2 { return; }
    let mut i = n - 2;
    while i >= 0 && arr[i] >= arr[i + 1] {
        if i == 0 { break; }
        i -= 1;
    }
    if arr[i] < arr[i + 1] {
        let mut j = n - 1;
        while arr[j] <= arr[i] {
            j -= 1;
        }
        arr.swap(i, j);
    }
    arr[i + 1..].reverse();
}

fn main() {
    let mut arr = vec![1, 2, 3];
    next_permutation(&mut arr);
    print!("Next Permutation: ");
    for val in arr {
        print!("{} ", val);
    }
}

fun nextPermutation(arr: IntArray) {
    var i = arr.size - 2
    while (i >= 0 && arr[i] >= arr[i + 1]) i--
    if (i >= 0) {
        var j = arr.size - 1
        while (arr[j] <= arr[i]) j--
        arr[i] = arr[j].also { arr[j] = arr[i] }
    }
    arr.setRange(i + 1, arr.size, arr.sliceArray(i + 1 until arr.size).reversed().toIntArray())
}

fun main() {
    val arr = intArrayOf(1, 2, 3)
    nextPermutation(arr)
    print("Next Permutation: ")
    println(arr.joinToString(" "))
}

func nextPermutation(_ nums: inout [Int]) {
    var i = nums.count - 2
    while i >= 0 && nums[i] >= nums[i + 1] {
        i -= 1
    }
    if i >= 0 {
        var j = nums.count - 1
        while nums[j] <= nums[i] {
            j -= 1
        }
        nums.swapAt(i, j)
    }
    nums[(i + 1)...] = nums[(i + 1)...].reversed()
}

var arr = [1, 2, 3]
nextPermutation(&arr)
print("Next Permutation:", terminator: " ")
print(arr.map { String($0) }.joined(separator: " "))

function nextPermutation(arr: number[]): number[] {
    let i = arr.length - 2;
    while (i >= 0 && arr[i] >= arr[i + 1]) i--;
    if (i >= 0) {
        let j = arr.length - 1;
        while (arr[j] <= arr[i]) j--;
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }
    let left = i + 1, right = arr.length - 1;
    while (left < right) {
        [arr[left], arr[right]] = [arr[right], arr[left]];
        left++;
        right--;
    }
    return arr;
}

const arr: number[] = [1, 2, 3];
console.log("Next Permutation:", nextPermutation(arr));

Time complexity

Space complexity

O(1)

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