Next Permutation of Array in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Next Permutation on a simple array

What is the output of the following C++ code that applies next permutation on the array?

DSA C++

std::vector<int> nums = {1, 2, 3};
std::next_permutation(nums.begin(), nums.end());
for (int n : nums) std::cout << n << " ";

A 2 1 3

B 3 2 1

C 1 2 3

D 1 3 2

💡 Hint

Next permutation finds the next lexicographically greater arrangement.

The next permutation after 1 2 3 is 1 3 2 because it is the next bigger sequence in order.

❓ Predict Output

intermediate

Next Permutation output on descending array

What will be printed after applying next permutation on this array?

DSA C++

std::vector<int> nums = {3, 2, 1};
std::next_permutation(nums.begin(), nums.end());
for (int n : nums) std::cout << n << " ";

A 3 2 1

B 3 1 2

C 1 2 3

D 2 3 1

💡 Hint

If the array is in descending order, next permutation resets to ascending order.

The array {3,2,1} is the highest permutation. Next permutation resets it to the lowest: {1,2,3}.

🔧 Debug

advanced

Identify the error in this next permutation implementation

What error will this code cause when run?

DSA C++

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

int main() {
  std::vector<int> arr = {3, 2, 1};
  nextPermutation(arr);
  for (int n : arr) std::cout << n << " ";
}

A Compilation error due to missing header

B Output: 1 2 3

C Runtime error due to invalid reverse range

D Output: 2 1 3

💡 Hint

Check the parameters passed to std::reverse carefully.

The reverse call should start from i+1 to reverse the suffix. The original code had an error using nums.begin() + i which included the pivot. Corrected code uses nums.begin() + i + 1.

🧠 Conceptual

advanced

Understanding the pivot in next permutation

In the next permutation algorithm, what is the role of the pivot index 'i' found by scanning from right to left?

A It marks the first element from the right that is smaller than its next element, indicating where to swap to get the next bigger permutation

B It marks the largest element in the array

C It marks the first element from the left that is greater than its previous element

D It marks the last element in the array to reverse

💡 Hint

Think about where the array stops increasing from the right.

The pivot 'i' is the first index from the right where nums[i] < nums[i+1]. This is where the next permutation changes by swapping and reversing the suffix.

❓ Predict Output

expert

Output after multiple next permutation calls

What is the output after applying next permutation three times on this array?

DSA C++

std::vector<int> nums = {1, 2, 3};
for (int i = 0; i < 3; i++) std::next_permutation(nums.begin(), nums.end());
for (int n : nums) std::cout << n << " ";

A 2 3 1

B 2 1 3

C 3 1 2

D 1 3 2

💡 Hint

List the permutations in order and count three steps from the start.

The permutations in order are: 1 2 3, 1 3 2, 2 1 3, 2 3 1, 3 1 2, 3 2 1. After three next_permutation calls from 1 2 3, the array is 2 3 1.

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