Next Permutation of Array in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output after applying next permutation?

Given the array [1, 3, 2], what will be the array after applying the next permutation algorithm once?

DSA Python

def next_permutation(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, right = i + 1, len(nums) - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

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

A [1, 3, 2]

B [2, 1, 3]

C [3, 1, 2]

D [1, 2, 3]

💡 Hint

Look for the first number from the right that is smaller than the number after it.

The next permutation swaps the first decreasing element from the right with the smallest larger element to its right, then reverses the suffix. For [1,3,2], the next permutation is [2,1,3].

❓ Predict Output

intermediate

What is the output after next permutation on a descending array?

What will be the output after applying the next permutation algorithm on the array [3, 2, 1]?

DSA Python

def next_permutation(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, right = i + 1, len(nums) - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

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

A [1, 2, 3]

B [3, 2, 1]

C [3, 1, 2]

D [2, 3, 1]

💡 Hint

If the array is in descending order, the next permutation is the smallest permutation.

The array [3,2,1] is the highest permutation. The next permutation resets it to the lowest, which is [1,2,3].

🔧 Debug

advanced

Identify the error in this next permutation implementation

What error will this code produce when run on input [1, 2, 3]?

DSA Python

def next_permutation(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, right = i + 1, len(nums) - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

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

A [1, 2, 3]

B [1, 3, 2]

C [3, 1, 2]

D IndexError

💡 Hint

Check the comparison operators in the while loops carefully.

The code uses '>' and '<' instead of '>=' and '<=' which can cause the inner while loop to decrement j below 0, causing IndexError.

🧠 Conceptual

advanced

How many permutations are possible for an array of length 4?

If you have an array of 4 distinct numbers, how many unique permutations can you generate?

A 16

B 8

C 24

D 12

💡 Hint

Think about factorial of the number of elements.

The number of unique permutations of n distinct elements is n! (n factorial). For 4 elements, 4! = 4 × 3 × 2 × 1 = 24.

🚀 Application

expert

Find the 5th next permutation of [1, 2, 3]

Starting from the array [1, 2, 3], what is the array after applying the next permutation algorithm 5 times in a row?

DSA Python

def next_permutation(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, right = i + 1, len(nums) - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

nums = [1, 2, 3]
for _ in range(5):
    next_permutation(nums)
print(nums)

A [3, 2, 1]

B [2, 3, 1]

C [3, 1, 2]

D [1, 3, 2]

💡 Hint

List all permutations in order and count 5 steps from the start.

The permutations of [1,2,3] in order are: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]. After 5 next permutations, we reach [3,2,1].