DEV Community

Manoj Kumar
Manoj Kumar

Posted on

Next Permutation – Python (Step-by-Step Explanation)

🔁 Next Permutation – Python (Step-by-Step Explanation)

Hi All,

Today I solved a very important problem: Next Permutation, which is commonly asked in coding interviews.

📌 Problem Statement

Given an array nums, rearrange it into the next lexicographically greater permutation.

👉 If such permutation is not possible, rearrange it into the lowest possible order (ascending).

🔍 Examples

Example 1: 

nums = [1, 2, 3]
Enter fullscreen mode Exit fullscreen mode

Output: 

[1, 3, 2]
Enter fullscreen mode Exit fullscreen mode

Example 2: 

nums = [3, 2, 1]
Enter fullscreen mode Exit fullscreen mode

Output: 

[1, 2, 3]
Enter fullscreen mode Exit fullscreen mode

Example 3: 

nums = [1, 1, 5]
Enter fullscreen mode Exit fullscreen mode

Output: 

[1, 5, 1]
Enter fullscreen mode Exit fullscreen mode

💡 Approach (Important!)

👉 This problem follows a pattern-based algorithm

🧠 Step-by-Step Logic

Step 1: Find the "break point"

  • Traverse from right
  • Find first index i such that: 
nums[i] < nums[i+1]
Enter fullscreen mode Exit fullscreen mode

Step 2: Find next greater element

  • Traverse from right again
  • Find element just greater than nums[i]
  • Swap them

Step 3: Reverse the remaining part

  • Reverse the array from i+1 to end

💻 Python Code 

def nextPermutation(nums):
    n = len(nums)

    # Step 1: Find break point
    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1

    # Step 2: Swap with next greater element
    if i >= 0:
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]

    # Step 3: Reverse the remaining part
    left = i + 1
    right = n - 1

    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1
Enter fullscreen mode Exit fullscreen mode

🔍 Dry Run

For:

nums = [1, 2, 3]
Enter fullscreen mode Exit fullscreen mode

Steps:

  • Break point → index 1 (2 < 3)
  • Swap → [1, 3, 2]
  • Reverse remaining → no change

Final Output:

[1, 3, 2]
Enter fullscreen mode Exit fullscreen mode

🖥️ Sample Output 

Input: [1,2,3]
Output: [1,3,2]

Input: [3,2,1]
Output: [1,2,3]

Input: [1,1,5]
Output: [1,5,1]
Enter fullscreen mode Exit fullscreen mode

⚡ Complexity Analysis

  • Time Complexity: O(n) ✅
  • Space Complexity: O(1) ✅

🧠 Why this is important?

  • Tests understanding of permutations
  • Uses in-place array manipulation
  • Very common in coding interviews

✅ Conclusion

This problem helped me understand:

  • Lexicographical ordering
  • In-place modifications
  • Pattern-based problem solving

🚀 A must-know problem for placements!

Top comments (0)