Next Permutation of Array in DSA Python

Mental Model

Find the next bigger arrangement of numbers by changing the smallest possible part of the array.

Analogy: Imagine you have a lock with digits. To get the next code, you try to increase the last digit. If it can't go higher, you move left to find a digit you can increase, then reset digits to the right to the smallest order.

Array: [1, 2, 3, 4, 5]
Indexes:  0  1  2  3  4
We want to find the next bigger order by changing digits from right to left.

Dry Run Walkthrough

Input: array: [1, 2, 3]

Goal: Find the next permutation which is just bigger than [1, 2, 3]

Step 1: Find the first index from right where array[i] < array[i+1], here i=1 (2 < 3)

[1, 2, 3] ↑i=1

Why: We need to find where the order breaks from the right to find the pivot to increase

Step 2: Find the first index from right where array[j] > array[i], here j=2 (3 > 2)

[1, 2, 3] ↑j=2

Why: We find the number just bigger than array[i] to swap and get next bigger permutation

Step 3: Swap array[i] and array[j], array becomes [1, 3, 2]

[1, 3, 2]

Why: Swapping increases the number at i to the next bigger digit

Step 4: Reverse the subarray after i (index 2 to end), here only one element so no change

[1, 3, 2]

Why: Reversing makes the tail the smallest possible order to get the next permutation

Result:

[1, 3, 2]

Annotated Code

DSA Python

from typing import List

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        n = len(nums)
        i = n - 2
        # Find first decreasing element from right
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1
        if i >= 0:
            j = n - 1
            # Find element just bigger than nums[i]
            while nums[j] <= nums[i]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]  # Swap
        # Reverse the tail
        left, right = i + 1, n - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

if __name__ == '__main__':
    arr = [1, 2, 3]
    Solution().nextPermutation(arr)
    print(arr)

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

Find the first index from right where order breaks (nums[i] < nums[i+1])

if i >= 0:

Check if such index exists, meaning next permutation is possible

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

Find the element just bigger than nums[i] from right

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

Swap to increase the number at i

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

Reverse the subarray after i to get the smallest tail order

Output

[1, 3, 2]

Complexity Analysis

Time: O(n) because we scan the array from right to left a few times but only once fully

Space: O(1) because we modify the array in place without extra space

vs Alternative: Naive approach would generate all permutations and find the next one, which is O(n!) and very inefficient

Edge Cases

array is in descending order like [3, 2, 1]

No next bigger permutation exists, so array is reversed to smallest order [1, 2, 3]

DSA Python

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

array has only one element like [1]

No change since only one permutation exists

DSA Python

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

array has repeated elements like [1, 5, 5]

Next permutation is found correctly by swapping and reversing tail

DSA Python

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

When to Use This Pattern

When you need to find the next bigger arrangement of numbers or characters in order, use the next permutation pattern because it efficiently finds the next lexicographical order.

Common Mistakes

Mistake: Not reversing the tail after swapping, leading to wrong next permutation
Fix: Always reverse the subarray after the swapped index to get the smallest tail order

Mistake: Swapping the wrong elements or not finding the correct pivot index
Fix: Carefully find the first decreasing element from right and then find the just bigger element to swap

Summary

Finds the next lexicographically bigger permutation of the array in place.

Use when you want to generate permutations in order or find the next bigger number with same digits.

The key is to find the pivot from right where order breaks, swap with just bigger element, then reverse the tail.

Practice

1. What does the next permutation of an array represent?

easy

A. The next lexicographically greater arrangement of the array elements

B. The array sorted in ascending order

C. The array reversed

D. The smallest element moved to the front

Solution

1. Step 1: Understand the concept of permutation order

   Permutations can be ordered lexicographically like words in a dictionary.

2. Step 2: Define next permutation meaning

   The next permutation is the next arrangement that is just greater than the current one in this order.

3. Final Answer:

   The next lexicographically greater arrangement of the array elements -> Option A

4. Quick Check:

   Next permutation = next bigger arrangement [OK]

Hint: Next permutation means next bigger order arrangement [OK]

Common Mistakes:

• Thinking next permutation is just sorting ascending
• Confusing next permutation with reversing the array
• Assuming next permutation always moves smallest element front

2. Which of the following Python code snippets correctly swaps two elements arr[i] and arr[j] in an array?

easy

A. arr[i], arr[j] = arr[j], arr[i]

B. arr[i] = arr[j]; arr[j] = arr[i]

C. swap(arr[i], arr[j])

D. arr[i] = arr[j]

Solution

1. Step 1: Recall Python tuple unpacking for swapping

   Python allows swapping two variables in one line using tuple unpacking.

2. Step 2: Check each option

   arr[i], arr[j] = arr[j], arr[i] correctly swaps using arr[i], arr[j] = arr[j], arr[i]. arr[i] = arr[j]; arr[j] = arr[i] overwrites arr[i] before assigning arr[j]. swap(arr[i], arr[j]) is invalid syntax without a defined function. arr[i] = arr[j] only assigns one element.

3. Final Answer:

   arr[i], arr[j] = arr[j], arr[i] -> Option A

4. Quick Check:

   Python swap uses tuple unpacking [OK]

Hint: Use tuple unpacking to swap in Python [OK]

Common Mistakes:

• Overwriting one element before swapping
• Using undefined swap function
• Assigning only one element instead of both

3. What is the output of the following code snippet?

arr = [1, 3, 2]
# Apply next permutation logic
# Step 1: Find first decreasing element from right (index 0)
# Step 2: Find element just larger than arr[0] from right (index 2)
# Step 3: Swap arr[0] and arr[2]
# Step 4: Reverse elements after index 0

arr[0], arr[2] = arr[2], arr[0]
arr[1:] = arr[1:][::-1]
print(arr)

medium

A. [3, 1, 2]

B. [2, 1, 3]

C. [1, 2, 3]

D. [2, 3, 1]

Solution

1. Step 1: Identify the first decreasing element from right

   From right, arr[1]=3 > arr[2]=2 (not decreasing), arr[0]=1 < arr[1]=3 (decreasing at index 0)

2. Step 2: Find element just larger than arr[0] from right

   From right, arr[2]=2 > arr[0]=1, so index 2 chosen

3. Step 3: Swap arr[0] and arr[2]

   Swap 1 and 2 -> arr becomes [2, 3, 1]

4. Step 4: Reverse elements after index 0

   Reverse arr[1:] -> arr[1:] = [3,1] reversed to [1,3]

5. Final Answer:

   [2, 1, 3] -> Option B

6. Quick Check:

   Next permutation of [1,3,2] = [2,1,3] [OK]

Hint: Swap pivot with next bigger, then reverse suffix [OK]

Common Mistakes:

• Not reversing suffix after swap
• Swapping wrong elements
• Confusing increasing and decreasing order

4. The following code attempts to find the next permutation of arr = [3, 2, 1]. What is the error?

def next_permutation(arr):
    i = len(arr) - 2
    while i >= 0 and arr[i] >= arr[i + 1]:
        i -= 1
    if i >= 0:
        j = len(arr) - 1
        while arr[j] <= arr[i]:
            j -= 1
        arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1:] = reversed(arr[i + 1:])

arr = [3, 2, 1]
next_permutation(arr)
print(arr)

medium

A. The while loop condition is incorrect

B. Swapping elements is done in wrong order

C. Using reversed() returns an iterator, not a list, causing wrong assignment

D. The function does not handle empty arrays

Solution

1. Step 1: Analyze the reversal line

   The line arr[i + 1:] = reversed(arr[i + 1:]) assigns an iterator to a list slice, which expects a list.

2. Step 2: Identify correct usage

   To assign reversed elements properly, convert iterator to list: arr[i + 1:] = list(reversed(arr[i + 1:])).

3. Final Answer:

   Using reversed() returns an iterator, not a list, causing wrong assignment -> Option C

4. Quick Check:

   reversed() needs list() for slice assignment [OK]

Hint: Use list(reversed(...)) when assigning slices [OK]

Common Mistakes:

• Assigning reversed() iterator directly to list slice
• Ignoring empty array edge case
• Swapping elements incorrectly

5. Given the array arr = [1, 5, 1], what is the next permutation after applying the standard algorithm? Consider duplicates carefully.

hard

A. [5, 1, 5]

B. [1, 1, 5]

C. [1, 5, 1]

D. [5, 1, 1]

Solution

1. Step 1: Find first decreasing element from right

   From right: arr[1]=5 > arr[2]=1 (not decreasing), arr[0]=1 < arr[1]=5 (decreasing at index 0)

2. Step 2: Find element just larger than arr[0] from right

   From right, arr[2]=1 not > 1, arr[1]=5 > 1, so index 1 chosen

3. Step 3: Swap arr[0] and arr[1]

   Swap 1 and 5 -> arr becomes [5, 1, 1]

4. Step 4: Reverse elements after index 0

   Reverse arr[1:] -> arr[1:] = [1,1] reversed is same [1,1]

5. Final Answer:

   [5, 1, 1] -> Option D

6. Quick Check:

   Duplicates handled, next permutation = [5,1,1] [OK]

Hint: Swap pivot with next bigger, reverse suffix even with duplicates [OK]

Common Mistakes:

• Ignoring duplicates when finding next bigger element
• Not reversing suffix after swap
• Assuming next permutation is sorted ascending always