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].

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