Next Permutation Explained Simply: Intuition, Algorithm, Dry Run, and Swift Solution

The Next Permutation problem looks confusing at first because the solution contains several steps that may feel unrelated:

• Find a pivot
• Find a greater element
• Swap
• Reverse part of the array

But once we understand why each step exists, the algorithm becomes much easier to remember.

In this article, I’ll explain the intuition behind Next Permutation step by step and implement it in Swift.

Problem Statement

Given an array of integers, rearrange the numbers into the next lexicographically greater permutation.

If such a permutation does not exist, rearrange the array into the smallest possible permutation.

For example:

123 → 132
132 → 213
213 → 231
231 → 312
312 → 321
321 → 123

Notice something important.

For 132, there are many permutations greater than it:

213
231
312
321

But the question does not ask for any greater permutation.

It asks for the next greater permutation.

Therefore:

132 → 213

This gives us the main idea behind the problem:

We need to make the number greater, but the increase should be as small as possible.

Understanding the Core Idea

Let’s take:

[1, 2, 5, 4, 3]

Think of it as:

12543

We need to find the smallest possible number greater than 12543 using exactly the same digits.

The algorithm can be understood using three questions:

1. Where is the rightmost position that can be increased?

2. What is the smallest greater value that can replace it?

3. After increasing it, how can we make everything after it as small as possible?

These three questions give us the complete algorithm.

Step 1: Find the Pivot

Start scanning from the right side of the array.

We are looking for the first position where:

nums[i - 1] < nums[i]

For:

[1, 2, 5, 4, 3]

Start from the right:

4 < 3 ❌

5 < 4 ❌

2 < 5 ✅

We found our pivot.

[1, 2, 5, 4, 3]
    ↑
  pivot

So:

pivot index = 1
pivot value = 2

But why is 2 the pivot?

Look at everything after 2:

5, 4, 3

This part is completely descending:

5 > 4 > 3

A descending arrangement is already the largest possible arrangement of those values.

For example, using 3, 4, and 5:

345
354
435
453
534
543

543 is the largest.

Therefore, we cannot create the next greater permutation by only rearranging:

5, 4, 3

We are forced to modify the number before it.

That number is:

2

This is our pivot.

Why Do We Search From the Right?

We want the next greater permutation, so we want to change the number as little as possible.

Changing something near the beginning causes a much bigger increase than changing something near the end.

For example:

12543

Changing the first digit would create a huge jump.

Instead, we want to find the rightmost possible position that can still be increased.

That’s why the pivot search starts from the right.

Swift Code for Finding the Pivot

var pivot = -1
let n = nums.count - 1

for i in stride(from: n, through: 1, by: -1) {
    if nums[i - 1] < nums[i] {
        pivot = i - 1
        break
    }
}

We initialize:

var pivot = -1

because -1 tells us:

No pivot has been found yet.

What If There Is No Pivot?

Consider:

[3, 2, 1]

Check from right:

2 < 1 ❌
3 < 2 ❌

There is no pivot.

Why?

Because:

321

is already the largest possible permutation.

The permutations are:

123
132
213
231
312
321

Since 321 is the last one, the next permutation should wrap around to the smallest:

123

So we simply reverse the entire array:

if pivot == -1 {
    nums.reverse()
    return
}

Example:

[3, 2, 1]

reverse

[1, 2, 3]

Step 2: Find the Smallest Greater Element

Let’s return to:

[1, 2, 5, 4, 3]

Our pivot is:

2

Now we need to increase 2.

The values on its right are:

5, 4, 3

All of them are greater than 2.

Which one should replace 2?

We could choose:

5
4
3

But remember our goal:

Make the smallest possible increase.

So the best choice is:

3

because it is the smallest value greater than 2.

Why Search From the Right Again?

Remember that everything after the pivot is descending:

5, 4, 3

If we read it from right to left:

3, 4, 5

we are effectively moving from smaller values toward larger values.

Therefore, the first element from the right that is greater than the pivot is exactly what we need.

Start:

pivot = 2

rightmost element = 3

3 > 2 ✅

So we swap 2 and 3.

Before:

[1, 2, 5, 4, 3]
    ↑        ↑

After:

[1, 3, 5, 4, 2]

Swift code:

var j = n

while j > pivot {
    if nums[j] > nums[pivot] {
        nums.swapAt(j, pivot)
        break
    }

    j -= 1
}

Notice the condition:

nums[j] > nums[pivot]

We need a strictly greater value.

Are We Finished After Swapping?

No.

This is one of the most important parts of the problem.

After swapping we have:

13542

Our original number was:

12543

13542 is definitely greater.

But is it the next greater permutation?

No.

For example:

13245

is also greater than:

12543

and:

13245 < 13542

Therefore, 13542 is too large.

We need one more step.

Step 3: Make the Suffix as Small as Possible

After swapping:

[1, 3, 5, 4, 2]

The important increase has already happened:

2 → 3

Now we want everything after 3 to contribute the smallest possible value.

Current suffix:

5, 4, 2

The smallest arrangement is:

2, 4, 5

So:

[1, 3, 5, 4, 2]

becomes

[1, 3, 2, 4, 5]

Therefore:

12543 → 13245

This is the next permutation.

Why Reverse Instead of Sort?

We already know that the suffix is descending.

Before swapping:

5, 4, 3

After swapping 3 with the pivot:

5, 4, 2

It is still descending.

To convert descending order into ascending order, we don’t need sorting.

We can simply reverse it:

5, 4, 2
   ↓
2, 4, 5

That gives us the smallest possible suffix.

Swift code:

var left = pivot + 1
var right = n

while left < right {
    nums.swapAt(left, right)
    left += 1
    right -= 1
}

Complete Dry Run: 132

Let’s take a smaller example.

[1, 3, 2]

We want the next permutation.

1. Find the pivot

Start from the right:

3 < 2 ❌

1 < 3 ✅

Therefore:

pivot index = 0
pivot value = 1

Visually:

[1, 3, 2]
 ↑
pivot

The suffix:

3, 2

is descending.

2. Find a greater element from the right

Start from the last element:

2 > 1 ✅

Swap 1 and 2:

[1, 3, 2]
 ↓
[2, 3, 1]

Now the permutation is greater, but we still need the smallest possible suffix.

3. Reverse everything after the pivot

Suffix:

3, 1

Reverse:

1, 3

Result:

[2, 1, 3]

Therefore:

132 → 213

Another Example: 123

Start:

[1, 2, 3]

Find pivot:

2 < 3 ✅

So:

pivot index = 1
pivot value = 2

Find greater element from the right:

3 > 2 ✅

Swap:

[1, 3, 2]

There is only one element after the pivot, so reversing changes nothing.

Result:

123 → 132

Example With Duplicates

Consider:

[1, 5, 1]

Find pivot:

5 < 1 ❌
1 < 5 ✅

So the pivot is the first 1.

Now search from the right for a value greater than 1.

1 > 1 ❌
5 > 1 ✅

Swap:

[5, 1, 1]

The suffix is already the smallest possible arrangement.

Therefore:

151 → 511

This also explains why we use:

nums[j] > nums[pivot]

instead of:

nums[j] >= nums[pivot]

The replacement must actually increase the permutation.

Complete Swift Solution

class Solution {
    func nextPermutation(_ nums: inout [Int]) {

        let n = nums.count - 1
        var pivot = -1

        // Step 1: Find the pivot
        for i in stride(from: n, through: 1, by: -1) {
            if nums[i - 1] < nums[i] {
                pivot = i - 1
                break
            }
        }

        // Array is already the largest permutation
        if pivot == -1 {
            nums.reverse()
            return
        }

        // Step 2: Find the first element greater
        // than the pivot while searching from right
        var j = n

        while j > pivot {
            if nums[j] > nums[pivot] {
                nums.swapAt(j, pivot)
                break
            }

            j -= 1
        }

        // Step 3: Reverse the suffix
        var left = pivot + 1
        var right = n

        while left < right {
            nums.swapAt(left, right)
            left += 1
            right -= 1
        }
    }
}

The Algorithm in Simple Words

Whenever I solve this problem, I think about it like this:

Find the rightmost position that can be increased.
                ↓
              PIVOT

Find the smallest greater value for that position.
                ↓
        SEARCH FROM THE RIGHT

Swap them.
                ↓

Make everything after the pivot as small as possible.
                ↓
          REVERSE THE SUFFIX

Or even shorter:

Find Pivot
    ↓
Find Greater
    ↓
Swap
    ↓
Reverse Suffix

The Real Intuition to Remember

Instead of memorizing four steps, remember one sentence:

Make the smallest possible change that makes the permutation greater.

We achieve that by:

1. Changing the rightmost possible position

This is why we find the pivot from the right.

2. Increasing it by the smallest possible amount

This is why we find the first greater element from the right.

3. Making the remaining part as small as possible

This is why we reverse the suffix.

For:

1 2 | 5 4 3
    ↑
  pivot

we first make the smallest increase:

1 2 5 4 3
    ↓
1 3 5 4 2

Then minimize everything after it:

1 3 | 5 4 2
        ↓
1 3 | 2 4 5

Final answer:

12543 → 13245

Time and Space Complexity

Time Complexity: O(n)

We perform at most three linear scans:

Find pivot        → O(n)
Find greater      → O(n)
Reverse suffix    → O(n)

Therefore:

O(n) + O(n) + O(n) = O(n)

Space Complexity: O(1)

We modify the array in place and only use a few variables.

Therefore:

Space = O(1)

Final Takeaway

Next Permutation initially looks like a problem where we need to generate permutations, but generating all permutations would be unnecessary and expensive.

The key observation is that the descending suffix tells us exactly where the current permutation stops being changeable.

From there, the strategy becomes:

Rightmost possible change
        +
Smallest possible increase
        +
Smallest possible suffix

which translates directly into:

Find Pivot → Find Greater → Swap → Reverse

Once this intuition is clear, there is much less to memorize.