Next Permutation of Array in DSA C++ - Time & Space Complexity

Time Complexity: Next Permutation of Array

O(n)

Understanding Time Complexity

We want to understand how the time needed to find the next permutation changes as the array size grows.

How does the number of steps grow when the array gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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());
}
    

This code finds the next lexicographical permutation of the array in place.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Two while loops scanning parts of the array and one reverse operation.
• How many times: Each loop runs at most once from the end towards the start, scanning up to n elements.

How Execution Grows With Input

As the array size grows, the loops may scan more elements, but each element is visited only a few times.

Input Size (n)	Approx. Operations
10	Up to about 30 steps
100	Up to about 300 steps
1000	Up to about 3000 steps

Pattern observation: The operations grow roughly in direct proportion to the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the next permutation grows linearly with the size of the array.

Common Mistake

[X] Wrong: "The algorithm checks all permutations, so it must be factorial time."

[OK] Correct: The algorithm only finds the very next permutation by scanning the array a few times, not generating all permutations.

Interview Connect

Understanding this linear time approach shows you can handle array scanning and in-place changes efficiently, a useful skill in many coding problems.

Self-Check

"What if we used a sorting step instead of reverse at the end? How would the time complexity change?"

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