Next Permutation Explained: Intuition, Algorithm, and Python Code (LeetCode 31)

Understanding Next Permutation (LeetCode 31)

While following a structured DSA roadmap, most of us get comfortable with patterns like Binary Search, Sliding Window, or Greedy. Then suddenly, a problem like Next Permutation appears — and it feels like it breaks that pattern-based thinking.

This is normal.

Next Permutation is not a typical pattern problem. It is a rule-based, observation-driven algorithm that relies on understanding lexicographical order rather than deriving a formula or recurrence.

---

Problem Statement

Given an array of integers, rearrange it into the next lexicographically greater permutation. If such an arrangement is not possible, rearrange it as the lowest possible order (sorted ascending).

The modification must be done in-place using only constant extra space.

---

Key Observations

• If the array is fully decreasing, it is already the largest permutation.
• The next permutation is formed by making the smallest possible increase.
• This increase always happens from the right side of the array.

---

Step-by-Step Intuition

1. Traverse from right to left and find the first index where nums[i] > nums[i-1]. This index marks the point where a larger permutation is possible.
2. If no such index exists, reverse the entire array to get the smallest permutation.
3. From the right side, find the smallest element greater than the breakpoint element and swap them.
4. Reverse the suffix after the breakpoint to make it as small as possible.

This guarantees the next lexicographical permutation with minimal change.

---

Python Implementation (In-Place)

class Solution:
    def nextPermutation(self, nums):
        idx = -1

        # Step 1: Find the breakpoint
        for i in range(len(nums) - 1, 0, -1):
            if nums[i] > nums[i - 1]:
                idx = i - 1
                break

        # Step 2: If no breakpoint, reverse entire array
        if idx == -1:
            nums.reverse()
            return

        # Step 3: Find element just larger than nums[idx]
        for i in range(len(nums) - 1, idx, -1):
            if nums[i] > nums[idx]:
                nums[i], nums[idx] = nums[idx], nums[i]
                break

        # Step 4: Reverse the suffix
        nums[idx + 1:] = reversed(nums[idx + 1:])

---

Why This Problem Feels Different

Most developers struggle with this problem at first because it cannot be derived using common DSA patterns. Almost everyone learns it by understanding the rules rather than discovering the solution independently.

That does not mean your problem-solving ability is weak — it means you are expanding your algorithmic vocabulary.

---

GitHub Reference

You can find the complete implementation here:

---

Final Thoughts

Next Permutation is a classic example of a problem that rewards observation over brute force. Once learned, it becomes a powerful tool — and a great confidence booster in interviews.

If this problem felt uncomfortable at first, that’s a good sign. Growth often feels that way.