Next Permutation of Array in DSA C++ - Execution Trace

Concept Flow - Next Permutation of Array

Start from end

↓

Find pivot i where arr[i

↓

If no pivot found

↓

Reverse whole array

→Done

No↓

Find successor j where arr[j

↓

Swap arr[i

↓

Reverse suffix from i+1 to end

↓

Done

Find the first decreasing element from the right, swap it with the next bigger element on the right, then reverse the suffix to get the next permutation.

Execution Sample

DSA C++

void nextPermutation(vector<int>& arr) {
  int i = arr.size() - 2;
  while (i >= 0 && arr[i] >= arr[i + 1]) i--;
  if (i >= 0) {
    int j = arr.size() - 1;
    while (arr[j] <= arr[i]) j--;
    swap(arr[i], arr[j]);
  }
  reverse(arr.begin() + i + 1, arr.end());
}

This code finds the next lexicographical permutation of the array.

Execution Table

Step	Operation	Pivot i	Successor j	Array State	Notes
1	Start from end, find pivot i where arr[i] < arr[i+1]	1	N/A	[1, 2, 3]	i=1 because arr[1]=2 < arr[2]=3
2	Find successor j where arr[j] > arr[i]	1	2	[1, 2, 3]	j=2 because arr[2]=3 > arr[1]=2
3	Swap arr[i] and arr[j]	1	2	[1, 3, 2]	Swap arr[1] and arr[2]
4	Reverse suffix from i+1 to end	1	2	[1, 3, 2]	Suffix after i=1 is [2], reversing no change
5	Done	1	2	[1, 3, 2]	Next permutation found
6	Start from end, find pivot i where arr[i] < arr[i+1]	-1	N/A	[3, 2, 1]	No pivot found, array is descending
7	Reverse whole array	N/A	N/A	[1, 2, 3]	Reversed to lowest permutation
8	Done	N/A	N/A	[1, 2, 3]	Next permutation is first permutation

💡 Stop when pivot not found or after reversing suffix to get next permutation

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 6	After Step 7	Final
i	N/A	1	1	1	1	-1	-1	-1
j	N/A	N/A	2	2	2	N/A	N/A	N/A
arr	[1,2,3]	[1,2,3]	[1,2,3]	[1,3,2]	[1,3,2]	[3,2,1]	[1,2,3]	[1,2,3]

Key Moments - 3 Insights

Why do we look for the pivot from the end and not from the start?

Because the next permutation changes the smallest suffix possible. The execution_table row 1 shows we find the first place from the right where the order breaks ascending, ensuring minimal change.

Why do we reverse the suffix after swapping?

The suffix after pivot is in descending order. Reversing it makes it ascending, which is the smallest order to get the next permutation. See execution_table row 4 for this step.

What happens if no pivot is found?

It means the array is in descending order, the highest permutation. We reverse the whole array to get the lowest permutation, as shown in execution_table rows 6 and 7.

Visual Quiz - 3 Questions

Look at the execution_table at step 1, what is the value of pivot i?

A 0

B 1

C 2

D -1

💡 Hint

Check the 'Pivot i' column in execution_table row 1.

At which step does the array get reversed because no pivot was found?

A Step 7

B Step 4

C Step 5

D Step 3

💡 Hint

Look at the 'Operation' column for reversing whole array in execution_table.

If the array was [1,3,2], what would be the pivot i found?

A -1

B 1

C 0

D 2

💡 Hint

Think about where arr[i] < arr[i+1] from the right side, similar to execution_table step 1.

Concept Snapshot

Next Permutation Algorithm:
1. Find pivot i from right where arr[i] < arr[i+1]
2. If no pivot, reverse whole array (lowest permutation)
3. Find successor j from right where arr[j] > arr[i]
4. Swap arr[i] and arr[j]
5. Reverse suffix from i+1 to end
Result: next lexicographically greater permutation

Full Transcript

The next permutation algorithm finds the next lexicographically greater arrangement of numbers. It starts from the end to find the first element that is smaller than its next element, called the pivot. If no such pivot exists, the array is the highest permutation and is reversed to the lowest. Otherwise, it finds the successor element just larger than the pivot, swaps them, and reverses the suffix after the pivot to get the next permutation. This process ensures the smallest change to get the next order.

Practice

1. What does the next_permutation function do to an array of integers?

easy

A. It rearranges the array to the next lexicographically greater permutation.

B. It sorts the array in ascending order.

C. It reverses the array elements.

D. It finds the maximum element in the array.

Solution

1. Step 1: Understand the purpose of next_permutation

   The function changes the array to the next bigger arrangement in dictionary order.

2. Step 2: Compare with other options

   Sorting or reversing are different operations; next_permutation specifically finds the next lexicographic order.

3. Final Answer:

   It rearranges the array to the next lexicographically greater permutation. -> Option A

4. Quick Check:

   Next permutation = next lexicographic order [OK]

Hint: Think of next_permutation as next dictionary word order [OK]

Common Mistakes:

• Confusing next_permutation with sorting
• Thinking it reverses the array
• Assuming it finds max element

2. Which of the following is the correct syntax to use std::next_permutation on a vector v in C++?

easy

A. std::next_permutation(v.begin(), v.end());

B. std::next_permutation(v);

C. next_permutation(v.begin(), v.end());

D. std::next_permutation(v.start(), v.finish());

Solution

1. Step 1: Recall the correct function signature

   std::next_permutation requires two iterators: begin and end of the container.

2. Step 2: Check each option

   std::next_permutation(v.begin(), v.end()); uses correct syntax with std:: and iterators. std::next_permutation(v); misses iterators. next_permutation(v.begin(), v.end()); misses std::. std::next_permutation(v.start(), v.finish()); uses invalid iterator names.

3. Final Answer:

   std::next_permutation(v.begin(), v.end()); -> Option A

4. Quick Check:

   Use std::next_permutation with begin() and end() [OK]

Hint: Always pass begin() and end() iterators to next_permutation [OK]

Common Mistakes:

• Omitting std:: namespace
• Passing container instead of iterators
• Using wrong iterator names like start() or finish()

3. What will be the output array after applying std::next_permutation once on arr = {1, 3, 2}?

medium

A. [2, 3, 1]

B. [1, 3, 2]

C. [1, 2, 3]

D. [2, 1, 3]

Solution

1. Step 1: Trace the next_permutation algorithm

   Array [1, 3, 2]. Find rightmost pivot i where arr[i] < arr[i+1]: i=0 (1 < 3).

2. Step 2: Find rightmost j > i with arr[j] > arr[i]

   j=2 (2 > 1). Swap i=0 and j=2: [2, 3, 1]. Reverse suffix from 1: [3, 1] -> [1, 3]. Result: [2, 1, 3].

3. Final Answer:

   [2, 1, 3] -> Option D

4. Quick Check:

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

Hint: Swap and reverse suffix to find next permutation [OK]

Common Mistakes:

• Confusing next with previous permutation
• Not reversing suffix after swap
• Assuming array stays same if not sorted

4. Consider the following code snippet:

std::vector<int> v = {3, 2, 1};
std::next_permutation(v.begin(), v.end());
for(int x : v) std::cout << x << ' ';

What is the output and why?

medium

A. 3 2 1

B. 1 2 3

C. 3 1 2

D. 2 3 1

Solution

1. Step 1: Recognize input is highest permutation

   The array [3, 2, 1] is sorted descending, so it's the last permutation.

2. Step 2: next_permutation resets to lowest permutation

   Since no next bigger permutation exists, it resets to ascending order [1, 2, 3].

3. Final Answer:

   1 2 3 -> Option B

4. Quick Check:

   Last permutation resets to first [OK]

Hint: Last permutation resets to ascending order [OK]

Common Mistakes:

• Expecting no change on last permutation
• Thinking next_permutation always swaps elements
• Ignoring reset behavior

5. Given the array arr = {1, 5, 4, 3, 2}, what is the next permutation after applying std::next_permutation?

hard

A. [1, 5, 2, 3, 4]

B. [1, 5, 4, 2, 3]

C. [2, 1, 3, 4, 5]

D. [1, 5, 4, 3, 2]

Solution

1. Step 1: Find the pivot from right where arr[i] < arr[i+1]

   arr=[1,5,4,3,2]. Check from right: i=3 (3<2? No), i=2 (4<3? No), i=1 (5<4? No), i=0 (1<5 Yes). Pivot=0.

2. Step 2: Find rightmost element > pivot (1) to swap

   Rightmost j>0 with arr[j]>1: j=4 (2>1). Swap 0 and 4: [2,5,4,3,1].

3. Step 3: Swap and reverse suffix

   Reverse suffix after 0: [5,4,3,1] -> [1,3,4,5]. Final: [2,1,3,4,5].

4. Final Answer:

   [2, 1, 3, 4, 5] -> Option C

5. Quick Check:

   Swap pivot and rightmost successor, then reverse suffix [OK]

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

Common Mistakes:

• Swapping wrong elements
• Not reversing suffix after swap
• Confusing pivot index