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.