Next Permutation of Array in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to find the next permutation by swapping the pivot with the right element.

DSA C++

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

Drag options to blanks, or click blank then click option'

Ai

Bj

C0

Di + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping with i or i+1 instead of j.

Not finding the correct j index.

We swap the element at index i (pivot) with the element at index j, which is the first element from the right greater than nums[i].

2fill in blank

medium

Complete the code to reverse the suffix of the array after the pivot index.

DSA C++

int start = i + 1;
int end = nums.size() - 1;
while (start < [1]) {
    std::swap(nums[start], nums[end]);
    start++;
    end--;
}

Drag options to blanks, or click blank then click option'

Anums.size()

Bstart

Ci

Dend

Attempts:

3 left

💡 Hint

Common Mistakes

Using start instead of end in the condition.

Looping until start <= end causing extra swaps.

We reverse the suffix by swapping elements from start to end until start meets end.

3fill in blank

hard

Fix the error in the loop that finds the pivot index where the next permutation changes.

DSA C++

int i = nums.size() - 2;
while (i >= 0 && nums[i] [1] nums[i + 1]) {
    i--;
}

Drag options to blanks, or click blank then click option'

A>=

B<

C<=

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' instead of '>=' causing wrong pivot detection.

Using '<=' or '>' which do not find the correct pivot.

We move left while nums[i] is greater than or equal to nums[i+1] to find the pivot where the order breaks.

4fill in blank

hard

Fill both blanks to correctly find the next permutation by swapping and reversing the suffix.

DSA C++

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

Drag options to blanks, or click blank then click option'

A>

B<

Cj

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' instead of '>' in the while condition.

Swapping with i instead of j.

We find j where nums[j] is greater than nums[i], then swap nums[i] and nums[j].

5fill in blank

hard

Fill all three blanks to implement the next permutation function correctly.

DSA C++

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

Drag options to blanks, or click blank then click option'

A>=

B<=

Cj

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong comparison operators in loops.

Swapping with wrong index.

The pivot is found by moving left while nums[i] >= nums[i+1]. Then j moves left while nums[j] <= nums[i]. Finally, swap nums[i] and nums[j].

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