Day 9 of 60 Days of DSA: Next Permutation of an Array (In-Place Algorithm)

A Classic Array Problem Frequently Asked in Google and Amazon Interviews

Why this Problem?

The Next Permutation problem is a staple in algorithm interviews because it demonstrates several key concepts:

Understanding lexicographical order
Thinking in terms of minimal and optimised changes
Recognising patterns in permutation problems

Mastering this problem helps you develop intuition for patterns in arrays and sequences — a skill useful in many technical questions.

Problem Description

Implement the next permutation, which rearranges numbers into the numerically next greater permutation of numbers for a given array A of size N.

If such arrangement is not possible, it must be rearranged as the lowest possible order, i.e., sorted in ascending order.

NOTE: The replacement must be in-place, do not allocate extra memory.

DO NOT USE LIBRARY FUNCTION FOR NEXT PERMUTATION.

Input/Output

Input 1: A = [1, 2, 3]

Output 1: [1, 3, 2]

Input 2: A = [3, 2, 1]

Output 2: [1, 2, 3]

Example Explanation

Explanation 1:

Next permutaion of [1, 2, 3] will be [1, 3, 2].

Explanation 2:

No arrangement is possible such that the number are arranged into the numerically next greater permutation of numbers.

So will rearranges it in the lowest possible order.

Approaches

1. Brute Force Approach

Idea

Generate all permutations of the array.
Store them in a list and sort them lexicographically.
Find the current permutation in this list.
Return the permutation that comes immediately after it.
If none exists, return the first (smallest) permutation.

Complexity with Brute Force

Time Complexity: O(N! × N)
(Generating and comparing all permutations)
Space Complexity: O(N!)
(Storing all permutations)

This approach becomes impractical even for moderate values of N due to huge computational costs.

2. Optimised Approach

Intuition

Think of the array like a number game where we want the next bigger number arrangement, but we are only allowed to rearrange the numbers we already have.

Example

[1, 2, 3]

All possible arrangements (in order) are:

[1, 2, 3]
[1, 3, 2] ← next
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

So the next permutation of [1, 2, 3] is [1, 3, 2].

Step 1: Look from the right side

We always look from the right end because:

The right side changes faster
Small changes on the right give the next smallest bigger number

Example:

[1, 3, 2]
 ↑

Here, 3 > 2, so this part is already in descending order.
That means we cannot make it bigger just by changing the rightmost numbers.

Step 2: Find the number we can increase (Pivot)

Now we move left and look for a place where:

left number < right number

Example:

[1, 3, 2]
 ↑

Here:

1 < 3 → good!
This 1 is the number we can increase a little
This position is called the pivot

Step 3: Increase it in the smallest way possible

We now:

Look to the right of the pivot
Pick the smallest number that is bigger than the pivot

Example:

Pivot = 1
Right side = [3, 2]
Smallest number bigger than 1 = 2

Swap them:

[2, 3, 1]

Step 4: Make the rest as small as possible

After increasing the pivot:

The remaining numbers should be arranged in the smallest order
So we reverse the right part, as it was already in decreasing order

[2, 1, 3]

This is the next permutation.

One-Line Understanding

Increase the number from the right as little as possible, and keep the rest as small as possible.

Code (JavaScript)

// Rearranges the array into the next lexicographically greater permutation in-place
function nextPermutation(arr) {
 const pivotIndex = findPivotIndex(arr);

 if (pivotIndex >= 0) {
 const successorIndex = findSuccessorIndex(arr, pivotIndex);
 swapElements(arr, pivotIndex, successorIndex);
 }

 reverseSubarray(arr, pivotIndex + 1, arr.length - 1);
 return arr;
}

// Finds the rightmost index where the array stops being in non-increasing order
function findPivotIndex(arr) {
 for (let i = arr.length - 2; i >= 0; i--) {
 if (arr[i] < arr[i + 1]) {
 return i;
 }
 }
 return -1;
}

// Finds the smallest element to the right of the pivot that is greater than the pivot
function findSuccessorIndex(arr, pivotIndex) {
 for (let i = arr.length - 1; i > pivotIndex; i--) {
 if (arr[i] > arr[pivotIndex]) {
 return i;
 }
 }
}

// Swaps the elements at the given indices in the array
function swapElements(arr, i, j) {
 const temp = arr[i];
 arr[i] = arr[j];
 arr[j] = temp;
}

// Reverses the elements of the array between the given indices (inclusive)
function reverseSubarray(arr, left, right) {
 while (left < right) {
 swapElements(arr, left, right);
 left++;
 right--;
 }
}

Complexity Of Optimised Approach

Time Complexity — O(N) single pass and a suffix reversal

Space Complexity — O(1) in-place without extra space

That’s it for Day 9 🎯

We have explored one of the most important interview problems to compute the answer in linear time with constant space. This problem appears frequently in technical interviews, helping you demonstrate algorithmic thinking and in-place manipulation skills.

Do you want to solve more with us?

Then follow this series and share your progress in the comments.

If the topics are difficult for you to understand, then you can refer to the notes on my GitHub.

At Dev Simplified, We Value Your Feedback 📊

👉 Let us know how you’re finding this series so far. It motivates us to write and provide valuable content for you.

👉 Follow us to not miss any updates.

👉 Subscribe for free and join our growing community!