Next Permutation of Array in DSA C++

Mental Model

Find the next bigger arrangement of numbers by changing the smallest possible part of the array.

Analogy: Imagine you have a row of books sorted in a certain order. To find the next order, you look from right to left to find the first book that can be swapped with a bigger book to its right, then rearrange the books after it to the smallest order.

Array: [1] -> [2] -> [3] -> [4] -> [5]
Indexes:  0      1      2      3      4

Dry Run Walkthrough

Input: array: [1, 2, 3]

Goal: Find the next permutation after [1, 2, 3], which is the next bigger number arrangement

Step 1: Find the first index from right where array[i] < array[i+1], here i=1 (2 < 3)

[1] -> [2] -> [3]
          ↑

Why: We need to find the pivot where the next bigger permutation can start

Step 2: Find the first index from right where array[j] > array[i], here j=2 (3 > 2)

[1] -> [2] -> [3]
          ↑      ↑

Why: We find the number just bigger than pivot to swap

Step 3: Swap array[i] and array[j], array becomes [1, 3, 2]

[1] -> [3] -> [2]

Why: Swapping creates a bigger number

Step 4: Reverse the sub-array after i (index 2 to end), here only one element so no change

[1] -> [3] -> [2]

Why: Reversing makes the suffix the smallest possible order

Result:

Final array: [1] -> [3] -> [2]

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void nextPermutation(vector<int>& nums) {
    int i = (int)nums.size() - 2;
    // Find first decreasing element from right
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }
    if (i >= 0) {
        int j = (int)nums.size() - 1;
        // Find element just bigger than nums[i]
        while (nums[j] <= nums[i]) {
            j--;
        }
        swap(nums[i], nums[j]);
    }
    // Reverse the suffix
    reverse(nums.begin() + i + 1, nums.end());
}

int main() {
    vector<int> nums = {1, 2, 3};
    nextPermutation(nums);
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

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

Find pivot index i where nums[i] < nums[i+1]

if (i >= 0) { while (nums[j] <= nums[i]) { j--; } swap(nums[i], nums[j]); }

Find element just bigger than pivot and swap

reverse(nums.begin() + i + 1, nums.end());

Reverse suffix to get smallest order after pivot

Output

1 3 2 

Complexity Analysis

Time: O(n) because we scan the array from right to left a few times and reverse a suffix once

Space: O(1) because the changes are done in place without extra storage

vs Alternative: Naive approach would generate all permutations and find the next one, which is O(n!) and very inefficient

Edge Cases

Array sorted in descending order, e.g. [3, 2, 1]

No next bigger permutation exists, so array is reversed to smallest order [1, 2, 3]

DSA C++

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

Array with all identical elements, e.g. [2, 2, 2]

No next bigger permutation, array remains the same after reversal

DSA C++

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

Array with two elements, e.g. [1, 2]

Swaps to [2, 1] as next permutation

DSA C++

if (i >= 0) { ... swap ... }

When to Use This Pattern

When asked to find the next bigger arrangement of numbers or characters in order, use the next permutation pattern to find it efficiently.

Common Mistakes

Mistake: Not reversing the suffix after swapping, leading to incorrect next permutation
Fix: Always reverse the part of the array after the pivot index to get the smallest suffix

Mistake: Swapping with the wrong element that is not just bigger than pivot
Fix: Find the rightmost element greater than pivot to swap

Summary

Finds the next lexicographically bigger permutation of an array in place.

Use when you need to generate permutations in order or find the next arrangement.

The key is to find the pivot from right, swap with just bigger element, then reverse suffix.

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