Finding the Next Permutation of an Array in Python

Problem Explanation

A permutation is an arrangement of elements in a specific order.

Given an array nums, your task is to find the next permutation —
the next greater arrangement of numbers in lexicographical order.

If such an arrangement is not possible (i.e., the array is in descending order),
you must rearrange it into the smallest possible order (ascending).

Example:

• Input: nums = [1, 2, 3]
  Output: [1, 3, 2]

• Input: nums = [3, 2, 1]
  Output: [1, 2, 3]

---

Method Used: Next Permutation Algorithm (Step-based Approach)

Idea:

1. Find the first decreasing element from the right
2. Find the next greater element and swap
3. Reverse the remaining part

---

Why This Method?

• Time complexity: O(n)
• Space complexity: O(1) (in-place)
• Efficient and commonly asked in interviews

---

Python Code with Explanation

class Solution:
    def nextPermutation(self, nums):

Defines the function to modify the array in-place.

---

        i = len(nums) - 2

Start from the second last index.

---

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

Find the first index i where nums[i] < nums[i+1].
This identifies the point where the order breaks.

---

        if i >= 0:

Check if such an index exists.

---

            j = len(nums) - 1

Start from the end to find the next greater element.

---

            while nums[j] <= nums[i]:
                j -= 1

Find the element just greater than nums[i].

---

            nums[i], nums[j] = nums[j], nums[i]

Swap them.

---

        left = i + 1
        right = len(nums) - 1

Set pointers to reverse the remaining part.

---

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

Reverse the subarray after index i.

---

Complete Code

class Solution:
    def nextPermutation(self, nums):
        i = len(nums) - 2

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

        if i >= 0:
            j = len(nums) - 1
            while nums[j] <= nums[i]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]

        left = i + 1
        right = len(nums) - 1

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

---

Step-by-Step Example

Input:

[1, 2, 3]

Steps:

1. Find break point → 2
2. Find next greater → 3
3. Swap → [1, 3, 2]
4. Reverse remaining → already sorted

Output:

[1, 3, 2]

---

Time and Space Complexity

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

---

Key Takeaway

The Next Permutation algorithm efficiently generates the next greater arrangement using swapping and reversing, without generating all permutations.

---