Next Permutation of Array in DSA Python - Execution Trace

Concept Flow - Next Permutation of Array

Start from right end

↓

Find first pair i where nums[i

Yes↓

Find j from right where nums[j

↓

Swap nums[i

↓

Reverse subarray from i+1 to end

↓

Done - next permutation found

No↓

Reverse whole array - last permutation reached

Find the next bigger arrangement by swapping and reversing parts of the array starting from the right.

Execution Sample

DSA Python

nums = [1, 2, 3]
# Find i
for i in range(len(nums)-2, -1, -1):
    if nums[i] < nums[i+1]:
        break
else:
    i = -1
if i == -1:
    nums.reverse()
else:
    # Find j
    for j in range(len(nums)-1, i, -1):
        if nums[j] > nums[i]:
            break
    # Swap and reverse
    nums[i], nums[j] = nums[j], nums[i]
    nums[i+1:] = reversed(nums[i+1:])

This code finds the next permutation by locating indices i and j, swapping, then reversing the tail. If no i is found, it reverses the entire array.

Execution Table

Step	Operation	Index i	Index j	Array State	Pointer Changes	Visual State
1	Start	N/A	N/A	[1, 2, 3]	i and j not set	1 -> 2 -> 3 -> null
2	Find i where nums[i] < nums[i+1]	1	N/A	[1, 2, 3]	i=1 (nums[1]=2)	1 -> 2 -> 3 -> null
3	Find j where nums[j] > nums[i]	1	2	[1, 2, 3]	j=2 (nums[2]=3)	1 -> 2 -> 3 -> null
4	Swap nums[i] and nums[j]	1	2	[1, 3, 2]	Swapped nums[1] and nums[2]	1 -> 3 -> 2 -> null
5	Reverse subarray from i+1 to end	1	2	[1, 3, 2]	Reversed subarray nums[2:]	1 -> 3 -> 2 -> null
6	Done - next permutation found	1	2	[1, 3, 2]	Final array	1 -> 3 -> 2 -> null
7	If no i found, reverse whole array	N/A	N/A	[1, 2, 3]	Reversed entire array	1 -> 2 -> 3 -> null

💡 Execution stops after finding next permutation or reversing entire array if last permutation reached.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
i	N/A	1	1	1	1	1
j	N/A	N/A	2	2	2	2
nums	[1, 2, 3]	[1, 2, 3]	[1, 2, 3]	[1, 3, 2]	[1, 3, 2]	[1, 3, 2]

Key Moments - 3 Insights

Why do we search for i from right to left where nums[i] < nums[i+1]?

Because we want to find the first place from the end where the array stops increasing, indicating where we can make the next bigger permutation. See execution_table step 2.

Why do we reverse the subarray after swapping?

Because after swapping, the subarray to the right of i is in descending order. Reversing it makes it the smallest possible order, ensuring the next permutation is just one step bigger. See execution_table step 5.

What if no such i is found?

It means the array is in descending order, the last permutation. We reverse the whole array to get the smallest permutation. See execution_table step 7.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, what is the value of i and nums[i]?

A i=0, nums[i]=1

B i=2, nums[i]=3

C i=1, nums[i]=2

D i=1, nums[i]=3

💡 Hint

Check the 'Index i' and 'Pointer Changes' columns in execution_table row 2.

At which step does the array change from [1, 2, 3] to [1, 3, 2]?

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Look at the 'Array State' column and 'Operation' description in execution_table rows 3-5.

If the array was [3, 2, 1], what would happen according to the execution_table?

A Reverse the whole array

B No changes, already next permutation

C Find i and j and swap

D Only reverse subarray from i+1

💡 Hint

See execution_table step 7 for the case when no i is found.

Concept Snapshot

Next Permutation:
- Find i from right where nums[i] < nums[i+1]
- Find j from right where nums[j] > nums[i]
- Swap nums[i], nums[j]
- Reverse subarray from i+1 to end
- If no i, reverse whole array (smallest permutation)

Full Transcript

Next Permutation finds the next bigger arrangement of numbers by scanning from the right to find the first decreasing pair (i). Then it finds a number bigger than nums[i] (j) from the right, swaps them, and reverses the tail to get the smallest bigger permutation. If no such i exists, the array is the biggest permutation, so we reverse it to start over from the smallest. This process ensures we move to the next permutation in lexicographic order.

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