Next Permutation

Problem

Given an array, rearrange it into the next lexicographically greater permutation.
If no such permutation exists, rearrange it into the smallest possible order (sorted in ascending order).

The change has to be done in-place.

Strategy

At first, it feels like you need to generate all permutations and then pick the next one.

But that’s not practical.

Instead, I tried looking at the array from the right side.

Moving from right to left, find the first place where the order breaks
That’s the point where we can make a slightly bigger permutation
Swap it with the next larger element
Then reverse everything after it to make it as small as possible

So it becomes:
find where it breaks → swap → reverse

Code

class Solution:
    def nextPermutation(self, nums):
        n = len(nums)

        i = n - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1

        if i >= 0:
            j = n - 1
            while nums[j] <= nums[i]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]

        left, right = i + 1, n - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

Key Lines Explained

while i >= 0 and nums[i] >= nums[i+1]:
This finds the point where the sequence stops increasing from the right.
nums[i], nums[j] = nums[j], nums[i]
Swap with the next larger element to make the permutation just a bit bigger.
Reversing from i+1 to end
This ensures the remaining part is the smallest possible.

Why This Works

We’re not trying to create all permutations.

We’re just making the smallest possible change that results in a larger arrangement.

If that’s not possible (like in a completely decreasing array), we reset to the smallest order.

Complexity

Time: O(n)
Space: O(1)

Final Note

This problem doesn’t feel obvious at first.

But once you start looking at the array from the right and focus on where the order changes, the steps become clear and repeatable.

DEV Community

Next Permutation