Next Permutation of Array in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the purpose of the Next Permutation algorithm?

It finds the next lexicographically greater permutation of an array of numbers. If no such permutation exists (the array is in descending order), it rearranges the array to the smallest permutation (ascending order).

intermediate

In the Next Permutation algorithm, what is the significance of finding the first index i from the right where nums[i] < nums[i+1]?

This index i marks the pivot point where the array stops decreasing from the right. It identifies where we can make a change to get a larger permutation.

intermediate

After finding the pivot index i, what is the next step in the Next Permutation algorithm?

Find the first index j from the right such that nums[j] > nums[i], then swap nums[i] and nums[j]. This step creates a slightly larger permutation.

intermediate

Why do we reverse the subarray after index i in the Next Permutation algorithm?

Because the subarray after i is in descending order, reversing it makes it ascending, which gives the smallest possible suffix and thus the next immediate larger permutation.

beginner

What happens if the entire array is in descending order when applying the Next Permutation algorithm?

It means the current permutation is the largest possible. The algorithm reverses the entire array to transform it into the smallest permutation (ascending order).

What does the Next Permutation algorithm do if the array is already the highest permutation?

A Reverses the array to the lowest permutation

B Leaves the array unchanged

C Sorts the array in descending order

D Swaps the first two elements

If the array is the highest permutation (descending order), the algorithm reverses it to get the lowest permutation (ascending order).

In the Next Permutation algorithm, what is the role of the pivot index i?

A It marks where the array starts to decrease from the right

B It is the index of the smallest element

C It is the index of the largest element

D It marks where the array stops decreasing from the right

The pivot index i is the first index from the right where nums[i] < nums[i+1], marking where the array stops decreasing from the right.

After swapping nums[i] and nums[j], what must be done next?

A Reverse the subarray after index <code>i</code>

B Do nothing

C Swap the first and last elements

D Sort the entire array

Reversing the subarray after i ensures the suffix is the smallest possible, giving the next permutation.

Which of these best describes the time complexity of the Next Permutation algorithm?

A O(n log n)

B O(n)

C O(n^2)

D O(1)

The algorithm scans the array a few times linearly, so the time complexity is O(n).

What is the first step in the Next Permutation algorithm?

A Reverse the entire array

B Find the first index from the left where the array is increasing

C Find the first index from the right where <code>nums[i] &lt; nums[i+1]</code>

D Swap the first two elements

The first step is to find the pivot index i scanning from the right where nums[i] < nums[i+1].

Explain the steps of the Next Permutation algorithm in your own words.

Think about how to get the next bigger arrangement of numbers.

Why do we reverse the subarray after the pivot index in the Next Permutation algorithm?

Consider how to get the smallest suffix after making the swap.

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